SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Point-set registration</title>

</head>

Point-set registration

</h1>

</header>

In <a href="Computer_vision" title="Computer vision">computer vision</a>, <a href="Pattern_recognition" title="Pattern recognition">pattern recognition</a>, and <a href="Robotics_engineering" title="Robotics engineering">robotics</a>, point-set registration, also known as point-cloud registration or scan matching, is the process of finding a spatial <a href="Mathematical_transformation" class="mw-redirect" title="Mathematical transformation">transformation</a> (e.g., <a href="Scaling_(geometry)" title="Scaling (geometry)">scaling</a>, <a href="Rotation" title="Rotation">rotation</a> and <a href="Translation_(geometry)" title="Translation (geometry)">translation</a>) that aligns two <a href="Point_cloud" title="Point cloud">point clouds</a>. The purpose of finding such a transformation includes merging multiple data sets into a globally consistent model (or coordinate frame), and mapping a new measurement to a known data set to identify features or to <a href="3D_pose_estimation" title="3D pose estimation">estimate its pose</a>. Raw 3D point cloud data are typically obtained from <a href="Lidar" title="Lidar">Lidars</a> and <a href="RGB-D_camera" class="mw-redirect" title="RGB-D camera">RGB-D cameras</a>. 3D point clouds can also be generated from computer vision algorithms such as <a href="Triangulation_(computer_vision)" title="Triangulation (computer vision)">triangulation</a>, <a href="Bundle_adjustment" title="Bundle adjustment">bundle adjustment</a>, and more recently, monocular image depth estimation using <a href="Deep_learning" title="Deep learning">deep learning</a>. For 2D point set registration used in image processing and feature-based <a href="Image_registration" title="Image registration">image registration</a>, a point set may be 2D pixel coordinates obtained by <a href="Feature_extraction" class="mw-redirect" title="Feature extraction">feature extraction</a> from an image, for example <a href="Corner_detection" title="Corner detection">corner detection</a>. Point cloud registration has extensive applications in <a href="Self-driving_car" title="Self-driving car">autonomous driving</a>,<a href="#cite_note-1">[1]</a> <a href="3D_reconstruction" title="3D reconstruction">motion estimation and 3D reconstruction</a>,<a href="#cite_note-2">[2]</a> <a href="Object_detection" title="Object detection">object detection and pose estimation</a>,<a href="#cite_note-3">[3]</a><a href="#cite_note-:4-4">[4]</a> <a href="Robotic_manipulation" class="mw-redirect" title="Robotic manipulation">robotic manipulation</a>,<a href="#cite_note-5">[5]</a> <a href="Simultaneous_localization_and_mapping" title="Simultaneous localization and mapping">simultaneous localization and mapping</a> (SLAM),<a href="#cite_note-6">[6]</a><a href="#cite_note-7">[7]</a> <a href="Image_stitching" title="Image stitching">panorama stitching</a>,<a href="#cite_note-:6-8">[8]</a> <a href="Virtual_reality" title="Virtual reality">virtual and augmented reality</a>,<a href="#cite_note-9">[9]</a> and <a href="Medical_imaging" title="Medical imaging">medical imaging</a>.<a href="#cite_note-10">[10]</a>

As a special case, registration of two point sets that only differ by a 3D rotation (i.e., there is no scaling and translation), is called the <a href="Wahba's_problem" title="Wahba's problem">Wahba Problem</a> and also related to the <a href="Orthogonal_Procrustes_problem" title="Orthogonal Procrustes problem">orthogonal procrustes problem</a>.

<div class="mw-heading mw-heading2"><h2 id="Formulation">Formulation</h2></div>

The problem may be summarized as follows:<a href="#cite_note-gmmjian-11">[11]</a>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lbrace {\mathcal {M}},{\mathcal {S}}\rbrace }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lbrace {\mathcal {M}},{\mathcal {S}}\rbrace }</annotation>

</semantics>

</math><img src="./dbc6b377301c45bbd0fb26e72a1dd9753a6d689b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.642ex; height:2.843ex;" alt="{\displaystyle \lbrace {\mathcal {M}},{\mathcal {S}}\rbrace }" loading="lazy"> be two finite size point sets <a href="Set_membership" class="mw-redirect" title="Set membership">in</a> a finite-dimensional real vector space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{d}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{d}}</annotation>

</semantics>

</math><img src="./a713426956296f1668fce772df3c60b9dde8a685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.77ex; height:2.676ex;" alt="{\displaystyle \mathbb {R} ^{d}}" loading="lazy">, which contain <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> points respectively (e.g., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=3}</annotation>

</semantics>

</math><img src="./58a4a6128b5cc1e25fcba3a16cbd9126b2d3e2fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.477ex; height:2.176ex;" alt="{\displaystyle d=3}" loading="lazy"> recovers the typical case of when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy"> are 3D point sets). The problem is to find a transformation to be applied to the moving "model" point set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> such that the difference (typically defined in the sense of point-wise <a href="Euclidean_distance" title="Euclidean distance">Euclidean distance</a>) between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> and the static "scene" set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy"> is minimized. In other words, a mapping from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{d}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{d}}</annotation>

</semantics>

</math><img src="./a713426956296f1668fce772df3c60b9dde8a685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.77ex; height:2.676ex;" alt="{\displaystyle \mathbb {R} ^{d}}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{d}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{d}}</annotation>

</semantics>

</math><img src="./a713426956296f1668fce772df3c60b9dde8a685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.77ex; height:2.676ex;" alt="{\displaystyle \mathbb {R} ^{d}}" loading="lazy"> is desired which yields the best alignment between the transformed "model" set and the "scene" set. The mapping may consist of a rigid or non-rigid transformation. The transformation model may be written as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy">, using which the transformed, registered model point set is:

/* start https://en.wikipedia.org/ */

.mw-parser-output table.numblk{border-collapse:collapse;border:none;margin-top:0;margin-right:0;margin-bottom:0}.mw-parser-output table.numblk>tbody>tr>td{vertical-align:middle;padding:0}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2){width:99%}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table{border-collapse:collapse;margin:0;border:none;width:100%}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:first-child,.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:last-child{padding:0 0.4ex}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:nth-child(2){width:100%;padding:0}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{padding:0}.mw-parser-output table.numblk>tbody>tr>td:last-child{font-weight:bold}.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child{font-weight:unset}.mw-parser-output table.numblk>tbody>tr>td:last-child::before{content:"("}.mw-parser-output table.numblk>tbody>tr>td:last-child::after{content:")"}.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child::before,.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child::after{content:none}.mw-parser-output table.numblk>tbody>tr>td{border:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td{border:thin solid}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td{border:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td{border:thin solid}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{border-left:none;border-right:none;border-bottom:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{border-left:thin solid;border-right:thin solid;border-bottom:thin solid}.mw-parser-output table.numblk:target{color:var(--color-base,#202122);background-color:#cfe8fd}@media screen{html.skin-theme-clientpref-night .mw-parser-output table.numblk:target{color:var(--color-base,#eaecf0);background-color:#301702}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output table.numblk:target{color:var(--color-base,#eaecf0);background-color:#301702}}

/* end https://en.wikipedia.org/ */

</style><table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T({\mathcal {M}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T({\mathcal {M}})}</annotation>

</semantics>

</math><img src="./9c0ed35c0344733e7c6cb4f49222b835582ca4af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.236ex; height:2.843ex;" alt="{\displaystyle T({\mathcal {M}})}" loading="lazy"></td> <td></td> <td class="nowrap">1</td></tr></tbody></table>

The output of a point set registration algorithm is therefore the optimal transformation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T^{\star }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T^{\star }}</annotation>

</semantics>

</math><img src="./3989633622d59e05ce5c4309cac4d33a50424ba2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.774ex; height:2.343ex;" alt="{\displaystyle T^{\star }}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> is best aligned to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy">, according to some defined notion of distance function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {dist} (\cdot ,\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {dist} (\cdot ,\cdot )}</annotation>

</semantics>

</math><img src="./596b9dba9db5f3b0ad8cd1963be72166a61844b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.897ex; height:2.843ex;" alt="{\displaystyle \operatorname {dist} (\cdot ,\cdot )}" loading="lazy">:

<msup>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T^{\star }=\arg \min _{T\in {\mathcal {T}}}{\text{dist}}(T({\mathcal {M}}),{\mathcal {S}})}</annotation>

</semantics>

</math><img src="./1a240e951ec5920a92a5151da7aa212aafc594d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:28.091ex; height:4.176ex;" alt="{\displaystyle T^{\star }=\arg \min _{T\in {\mathcal {T}}}{\text{dist}}(T({\mathcal {M}}),{\mathcal {S}})}" loading="lazy"></td> <td></td> <td class="nowrap">2</td></tr></tbody></table>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {T}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {T}}}</annotation>

</semantics>

</math><img src="./8236d074e42310f5dc24d1d2b5b8f5981c3e87ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.936ex; height:2.343ex;" alt="{\displaystyle {\mathcal {T}}}" loading="lazy"> is used to denote the set of all possible transformations that the optimization tries to search for. The most popular choice of the distance function is to take the square of the <a href="Euclidean_distance" title="Euclidean distance">Euclidean distance</a> for every pair of points:

</mrow>

</mrow>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {dist} (T({\mathcal {M}}),{\mathcal {S}})=\sum _{m\in T({\mathcal {M}})}\Vert m-s_{m}\Vert _{2}^{2},\quad s_{m}=\arg \min _{s\in {\mathcal {S}}}\Vert s-m\Vert _{2}^{2}}</annotation>

</semantics>

</math><img src="./201815d8b44c6aefbd72945d092fcec59dc940e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:62.248ex; height:6.009ex;" alt="{\displaystyle \operatorname {dist} (T({\mathcal {M}}),{\mathcal {S}})=\sum _{m\in T({\mathcal {M}})}\Vert m-s_{m}\Vert _{2}^{2},\quad s_{m}=\arg \min _{s\in {\mathcal {S}}}\Vert s-m\Vert _{2}^{2}}" loading="lazy"></td> <td></td> <td class="nowrap">3</td></tr></tbody></table>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|\cdot \|_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|\cdot \|_{2}}</annotation>

</semantics>

</math><img src="./b3a8e44a2eb980f856968a6357e3d0a7c22c905f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.058ex; height:2.843ex;" alt="{\displaystyle \|\cdot \|_{2}}" loading="lazy"> denotes the <a href="Norm_(mathematics)" title="Norm (mathematics)">vector 2-norm</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{m}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{m}}</annotation>

</semantics>

</math><img src="./5afa6f6448663982b8719f5c6223e7212577a06a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.765ex; height:2.009ex;" alt="{\displaystyle s_{m}}" loading="lazy"> is the <a href="Corresponding_point" class="mw-redirect" title="Corresponding point">corresponding point</a> in set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy"> that attains the shortest distance to a given point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> in set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> after transformation. Minimizing such a function in rigid registration is equivalent to solving a <a href="Least_squares" title="Least squares">least squares</a> problem.

<div class="mw-heading mw-heading2"><h2 id="Types_of_algorithms">Types of algorithms</h2></div>

When the correspondences (i.e., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{m}\leftrightarrow m}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{m}\leftrightarrow m}</annotation>

</semantics>

</math><img src="./9c933be28fca074ff165376c92dd95b5744c7894.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.42ex; height:2.176ex;" alt="{\displaystyle s_{m}\leftrightarrow m}" loading="lazy">) are given before the optimization, for example, using <a href="Feature_matching" class="mw-redirect" title="Feature matching">feature matching</a> techniques, then the optimization only needs to estimate the transformation. This type of registration is called correspondence-based registration. On the other hand, if the correspondences are unknown, then the optimization is required to jointly find out the correspondences and transformation together. This type of registration is called simultaneous pose and correspondence registration.

<div class="mw-heading mw-heading3"><h3 id="Rigid_registration">Rigid registration</h3></div>

Given two point sets, rigid registration yields a <a href="Rigid_transformation" title="Rigid transformation">rigid transformation</a> which maps one point set to the other. A rigid transformation is defined as a transformation that does not change the distance between any two points. Typically such a transformation consists of <a href="Translation_(geometry)" title="Translation (geometry)">translation</a> and <a href="Rotation" title="Rotation">rotation</a>.<a href="#cite_note-lmfitzgibbon-12">[12]</a> In rare cases, the point set may also be mirrored. In robotics and computer vision, rigid registration has the most applications.

<div class="mw-heading mw-heading3"><h3 id="Non-rigid_registration">Non-rigid registration</h3></div>

Given two point sets, non-rigid registration yields a non-rigid transformation which maps one point set to the other. Non-rigid transformations include <a href="Affine_transformations" class="mw-redirect" title="Affine transformations">affine transformations</a> such as <a href="Scaling_(geometry)" title="Scaling (geometry)">scaling</a> and <a href="Shear_mapping" title="Shear mapping">shear mapping</a>. However, in the context of point set registration, non-rigid registration typically involves nonlinear transformation. If the <a href="Eigenmode" class="mw-redirect" title="Eigenmode">eigenmodes of variation</a> of the point set are known, the nonlinear transformation may be parametrized by the eigenvalues.<a href="#cite_note-cpdmyronenko2-13">[13]</a> A nonlinear transformation may also be parametrized as a <a href="Thin_plate_spline" title="Thin plate spline">thin plate spline</a>.<a href="#cite_note-tpsrpmchui-14">[14]</a><a href="#cite_note-cpdmyronenko2-13">[13]</a>

<div class="mw-heading mw-heading3"><h3 id="Other_types">Other types</h3></div>

Some approaches to point set registration use algorithms that solve the more general <a href="Graph_matching" title="Graph matching">graph matching</a> problem.<a href="#cite_note-gmmjian-11">[11]</a> However, the computational complexity of such methods tend to be high and they are limited to rigid registrations.

In this article, we will only consider algorithms for rigid registration, where the transformation is assumed to contain 3D rotations and translations (possibly also including a uniform scaling).

The <a href="PCL_(Point_Cloud_Library)" class="mw-redirect" title="PCL (Point Cloud Library)">PCL (Point Cloud Library)</a> is an open-source framework for n-dimensional point cloud and 3D geometry processing. It includes several point registration algorithms.<a href="#cite_note-PCL-Tutorial-15">[15]</a>

<div class="mw-heading mw-heading2"><h2 id="Correspondence-based_registration">Correspondence-based registration</h2></div>

Correspondence-based methods assume the putative correspondences <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\leftrightarrow s_{m}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\leftrightarrow s_{m}}</annotation>

</semantics>

</math><img src="./ccce4b9f38d245a6bfb9afc8acb56d6c68852e01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.42ex; height:2.176ex;" alt="{\displaystyle m\leftrightarrow s_{m}}" loading="lazy"> are given for every point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\in {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\in {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./28209c1c5ccb90f01b15b6328b9bf50cfc8d5592.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.672ex; height:2.176ex;" alt="{\displaystyle m\in {\mathcal {M}}}" loading="lazy">. Therefore, we arrive at a setting where both point sets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy"> have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> points and the correspondences <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}\leftrightarrow s_{i},i=1,\dots ,N}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{i}\leftrightarrow s_{i},i=1,\dots ,N}</annotation>

</semantics>

</math><img src="./f2cf189e9bd1ad1d07b32e370c38b9cd747dfaec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:21.683ex; height:2.509ex;" alt="{\displaystyle m_{i}\leftrightarrow s_{i},i=1,\dots ,N}" loading="lazy"> are given.

<div class="mw-heading mw-heading3"><h3 id="Outlier-free_registration">Outlier-free registration</h3></div>

In the simplest case, one can assume that all the correspondences are correct, meaning that the points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i},s_{i}\in \mathbb {R} ^{3}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{i},s_{i}\in \mathbb {R} ^{3}}</annotation>

</semantics>

</math><img src="./30795d3739f4a0e4b2cf1ae2ed4f12b7565baee6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.337ex; height:3.009ex;" alt="{\displaystyle m_{i},s_{i}\in \mathbb {R} ^{3}}" loading="lazy"> are generated as follows:<table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}=lRm_{i}+t+\epsilon _{i},i=1,\dots ,N}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}=lRm_{i}+t+\epsilon _{i},i=1,\dots ,N}</annotation>

</semantics>

</math><img src="./aa54416b37fda172d21b60b8ab43b493e9319455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:31.889ex; height:2.509ex;" alt="{\displaystyle s_{i}=lRm_{i}+t+\epsilon _{i},i=1,\dots ,N}" loading="lazy"></td> <td></td> <td class="nowrap">cb.1</td></tr></tbody></table>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l>0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l>0}</annotation>

</semantics>

</math><img src="./d0476eebc4457e538f82c70dd52b519075ae2754.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.954ex; height:2.176ex;" alt="{\displaystyle l>0}" loading="lazy"> is a uniform scaling factor (in many cases <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l=1}</annotation>

</semantics>

</math><img src="./8fc60b21200ebf2b338c4fa71b103cb697b02bd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.954ex; height:2.176ex;" alt="{\displaystyle l=1}" loading="lazy"> is assumed), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\in {\text{SO}}(3)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\in {\text{SO}}(3)}</annotation>

</semantics>

</math><img src="./57bd838390adf4248669587ed74523996465dcb2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.677ex; height:2.843ex;" alt="{\displaystyle R\in {\text{SO}}(3)}" loading="lazy"> is a proper 3D rotation matrix (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{SO}}(d)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{SO}}(d)}</annotation>

</semantics>

</math><img src="./c0c8fddb0c11bed893f21c42b7dbd795ba8c2002.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.126ex; height:2.843ex;" alt="{\displaystyle {\text{SO}}(d)}" loading="lazy"> is the <a href="Special_orthogonal_group" class="mw-redirect" title="Special orthogonal group">special orthogonal group</a> of degree <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\in \mathbb {R} ^{3}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\in \mathbb {R} ^{3}}</annotation>

</semantics>

</math><img src="./9037348263ce54ffc8a3f8f2392974b4eb07b9c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.413ex; height:2.676ex;" alt="{\displaystyle t\in \mathbb {R} ^{3}}" loading="lazy"> is a 3D translation vector and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon _{i}\in \mathbb {R} ^{3}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon _{i}\in \mathbb {R} ^{3}}</annotation>

</semantics>

</math><img src="./e61d2b7a4c55133253c534421e8a4a173659f824.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.317ex; height:3.009ex;" alt="{\displaystyle \epsilon _{i}\in \mathbb {R} ^{3}}" loading="lazy"> models the unknown additive noise (e.g., <a href="Gaussian_noise" title="Gaussian noise">Gaussian noise</a>). Specifically, if the noise <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon _{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon _{i}}</annotation>

</semantics>

</math><img src="./9be3140164b763359077d92b2cd33798eb6a488c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.744ex; height:2.009ex;" alt="{\displaystyle \epsilon _{i}}" loading="lazy"> is assumed to follow a zero-mean isotropic Gaussian distribution with standard deviation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma _{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{i}}</annotation>

</semantics>

</math><img src="./6ab3208a7d0c634ef720e03ff5a9949e8310edc4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.127ex; height:2.009ex;" alt="{\displaystyle \sigma _{i}}" loading="lazy">, i.e., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon _{i}\sim {\mathcal {N}}(0,\sigma _{i}^{2}I_{3})}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon _{i}\sim {\mathcal {N}}(0,\sigma _{i}^{2}I_{3})}</annotation>

</semantics>

</math><img src="./57bd786c2e73ea2d307cba064b55b6ea2be5b44f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.585ex; height:3.176ex;" alt="{\displaystyle \epsilon _{i}\sim {\mathcal {N}}(0,\sigma _{i}^{2}I_{3})}" loading="lazy">, then the following optimization can be shown to yield the <a href="Maximum_likelihood_estimation" title="Maximum likelihood estimation">maximum likelihood estimate</a> for the unknown scale, rotation and translation:<table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}{\frac {1}{\sigma _{i}^{2}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}^{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</munderover>

<mfrac>

</mrow>

</mrow>

</msubsup>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}{\frac {1}{\sigma _{i}^{2}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}^{2}}</annotation>

</semantics>

</math><img src="./9ea8b404544112c8485172667baa7b086fcab906.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:53.538ex; height:7.343ex;" alt="{\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}{\frac {1}{\sigma _{i}^{2}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}^{2}}" loading="lazy"></td> <td></td> <td class="nowrap">cb.2</td></tr></tbody></table>Note that when the scaling factor is 1 and the translation vector is zero, then the optimization recovers the formulation of the <a href="Wahba's_problem" title="Wahba's problem">Wahba problem</a>. Despite the <a href="Convex_optimization" title="Convex optimization">non-convexity</a> of the optimization (<a href="#math_cb.2">cb.2</a>) due to non-convexity of the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{SO}}(3)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{SO}}(3)}</annotation>

</semantics>

</math><img src="./76ea569dfd0b7e75a686925ff43ea07e50e79526.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.072ex; height:2.843ex;" alt="{\displaystyle {\text{SO}}(3)}" loading="lazy">, seminal work by <a href="Berthold_K.P._Horn" title="Berthold K.P. Horn">Berthold K.P. Horn</a> showed that (<a href="#math_cb.2">cb.2</a>) actually admits a closed-form solution, by decoupling the estimation of scale, rotation and translation.<a href="#cite_note-:11-16">[16]</a> Similar results were discovered by Arun et al.<a href="#cite_note-:12-17">[17]</a> In addition, in order to find a unique transformation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (l,R,t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (l,R,t)}</annotation>

</semantics>

</math><img src="./0635f40f1b7fcfac18ca6fb9f9ee5e91e76a7e7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.174ex; height:2.843ex;" alt="{\displaystyle (l,R,t)}" loading="lazy">, at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=3}</annotation>

</semantics>

</math><img src="./b4ab951d779fcdeea3ec188bb5c73518c46b19de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.325ex; height:2.176ex;" alt="{\displaystyle N=3}" loading="lazy"> non-collinear points in each point set are required.

More recently, Briales and Gonzalez-Jimenez have developed a <a href="Semidefinite_programming" title="Semidefinite programming">semidefinite relaxation</a> using <a href="Duality_(optimization)" title="Duality (optimization)">Lagrangian duality</a>, for the case where the model set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> contains different 3D primitives such as points, lines and planes (which is the case when the model <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> is a 3D mesh).<a href="#cite_note-18">[18]</a> Interestingly, the semidefinite relaxation is empirically tight, i.e., a certifiably <a href="Globally_optimal" class="mw-redirect" title="Globally optimal">globally optimal</a> solution can be extracted from the solution of the semidefinite relaxation.

<div class="mw-heading mw-heading3"><h3 id="Robust_registration">Robust registration</h3></div>

The <a href="Least_squares" title="Least squares">least squares</a> formulation (<a href="#math_cb.2">cb.2</a>) is known to perform arbitrarily badly in the presence of <a href="Outlier" title="Outlier">outliers</a>. An outlier correspondence is a pair of measurements <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}\leftrightarrow m_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}\leftrightarrow m_{i}}</annotation>

</semantics>

</math><img src="./ed2b329e778555dc8b21a32075a8f3a9334b9f62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.344ex; height:2.176ex;" alt="{\displaystyle s_{i}\leftrightarrow m_{i}}" loading="lazy"> that departs from the generative model (<a href="#math_cb.1">cb.1</a>). In this case, one can consider a different generative model as follows:<a href="#cite_note-:5-19">[19]</a><table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}={\begin{cases}lRm_{i}+t+\epsilon _{i}&{\text{if }}i-{\text{th pair is an inlier}}\\o_{i}&{\text{if }}i-{\text{th pair is an outlier}}\end{cases}}}">

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

<mtext>th pair is an inlier</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

<mtext>th pair is an outlier</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}={\begin{cases}lRm_{i}+t+\epsilon _{i}&{\text{if }}i-{\text{th pair is an inlier}}\\o_{i}&{\text{if }}i-{\text{th pair is an outlier}}\end{cases}}}</annotation>

</semantics>

</math><img src="./e42d9bb255858b59566e4964910781cb48b1da3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:48.098ex; height:6.176ex;" alt="{\displaystyle s_{i}={\begin{cases}lRm_{i}+t+\epsilon _{i}&{\text{if }}i-{\text{th pair is an inlier}}\\o_{i}&{\text{if }}i-{\text{th pair is an outlier}}\end{cases}}}" loading="lazy"></td> <td></td> <td class="nowrap">cb.3</td></tr></tbody></table>where if the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i-}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i-}</annotation>

</semantics>

</math><img src="./c7f6fad67c10ad729a7c66690989aedfdd72cfb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.611ex; height:2.343ex;" alt="{\displaystyle i-}" loading="lazy">th pair <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}\leftrightarrow m_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}\leftrightarrow m_{i}}</annotation>

</semantics>

</math><img src="./ed2b329e778555dc8b21a32075a8f3a9334b9f62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.344ex; height:2.176ex;" alt="{\displaystyle s_{i}\leftrightarrow m_{i}}" loading="lazy"> is an inlier, then it obeys the outlier-free model (<a href="#math_cb.1">cb.1</a>), i.e., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}}</annotation>

</semantics>

</math><img src="./cfda82668232cbdc0874ed28ab8b6079420d1ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.89ex; height:2.009ex;" alt="{\displaystyle s_{i}}" loading="lazy"> is obtained from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>

</semantics>

</math><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"> by a spatial transformation plus some small noise; however, if the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i-}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i-}</annotation>

</semantics>

</math><img src="./c7f6fad67c10ad729a7c66690989aedfdd72cfb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.611ex; height:2.343ex;" alt="{\displaystyle i-}" loading="lazy">th pair <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}\leftrightarrow m_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}\leftrightarrow m_{i}}</annotation>

</semantics>

</math><img src="./ed2b329e778555dc8b21a32075a8f3a9334b9f62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.344ex; height:2.176ex;" alt="{\displaystyle s_{i}\leftrightarrow m_{i}}" loading="lazy"> is an outlier, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}}</annotation>

</semantics>

</math><img src="./cfda82668232cbdc0874ed28ab8b6079420d1ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.89ex; height:2.009ex;" alt="{\displaystyle s_{i}}" loading="lazy"> can be any arbitrary vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o_{i}}</annotation>

</semantics>

</math><img src="./c81b6f1251a0d2e12011a746b586c5fa9a132d48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle o_{i}}" loading="lazy">. Since one does not know which correspondences are outliers beforehand, robust registration under the generative model (<a href="#math_cb.3">cb.3</a>) is of paramount importance for computer vision and robotics deployed in the real world, because current feature matching techniques tend to output highly corrupted correspondences where over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 95\%}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 95\%}</annotation>

</semantics>

</math><img src="./38c9a021d5d9cf23f5453ada8675575253243554.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.261ex; height:2.343ex;" alt="{\displaystyle 95\%}" loading="lazy"> of the correspondences can be outliers.<a href="#cite_note-:0-20">[20]</a>

Next, we describe several common paradigms for robust registration.

<div class="mw-heading mw-heading4"><h4 id="Maximum_consensus">Maximum consensus</h4></div>

<a href="Consensus_(computer_science)" title="Consensus (computer science)">Maximum consensus</a> seeks to find the largest set of correspondences that are consistent with the generative model (<a href="#math_cb.1">cb.1</a>) for some choice of spatial transformation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (l,R,t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (l,R,t)}</annotation>

</semantics>

</math><img src="./0635f40f1b7fcfac18ca6fb9f9ee5e91e76a7e7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.174ex; height:2.843ex;" alt="{\displaystyle (l,R,t)}" loading="lazy">. Formally speaking, maximum consensus solves the following optimization:<table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3},{\mathcal {I}}}\vert {\mathcal {I}}\vert ,\quad {\text{subject to }}{\frac {1}{\sigma _{i}^{2}}}\Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}\leq \xi ,\forall i\in {\mathcal {I}}}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

<mtext>subject to </mtext>

</mrow>

<mfrac>

</mrow>

</mrow>

</msubsup>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3},{\mathcal {I}}}\vert {\mathcal {I}}\vert ,\quad {\text{subject to }}{\frac {1}{\sigma _{i}^{2}}}\Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}\leq \xi ,\forall i\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./beac70bb684faefcd192ddeb67fb850ddf379972.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:64.202ex; height:6.343ex;" alt="{\displaystyle \max _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3},{\mathcal {I}}}\vert {\mathcal {I}}\vert ,\quad {\text{subject to }}{\frac {1}{\sigma _{i}^{2}}}\Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}\leq \xi ,\forall i\in {\mathcal {I}}}" loading="lazy"></td> <td></td> <td class="nowrap">cb.4</td></tr></tbody></table>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vert {\mathcal {I}}\vert }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vert {\mathcal {I}}\vert }</annotation>

</semantics>

</math><img src="./e06f9f0e45c5ac32be08c1e380b29f85f06c09a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.786ex; height:2.843ex;" alt="{\displaystyle \vert {\mathcal {I}}\vert }" loading="lazy"> denotes the <a href="Cardinality" title="Cardinality">cardinality</a> of the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy">. The constraint in (<a href="#math_cb.4">cb.4</a>) enforces that every pair of measurements in the inlier set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> must have <a href="Residuals_(statistics)" class="mw-redirect" title="Residuals (statistics)">residuals</a> smaller than a pre-defined threshold <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy">. Unfortunately, recent analyses have shown that globally solving problem (cb.4) is <a href="NP-hardness" title="NP-hardness">NP-Hard</a>, and global algorithms typically have to resort to <a href="Branch_and_bound" title="Branch and bound">branch-and-bound</a> (BnB) techniques that take exponential-time complexity in the worst case.<a href="#cite_note-:1-21">[21]</a><a href="#cite_note-:2-22">[22]</a><a href="#cite_note-:3-23">[23]</a><a href="#cite_note-24">[24]</a><a href="#cite_note-25">[25]</a>

Although solving consensus maximization exactly is hard, there exist efficient heuristics that perform quite well in practice. One of the most popular heuristics is the <a href="Random_sample_consensus" title="Random sample consensus">Random Sample Consensus (RANSAC)</a> scheme.<a href="#cite_note-26">[26]</a> RANSAC is an iterative hypothesize-and-verify method. At each iteration, the method first randomly samples 3 out of the total number of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> correspondences and computes a hypothesis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (l,R,t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (l,R,t)}</annotation>

</semantics>

</math><img src="./0635f40f1b7fcfac18ca6fb9f9ee5e91e76a7e7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.174ex; height:2.843ex;" alt="{\displaystyle (l,R,t)}" loading="lazy"> using Horn's method,<a href="#cite_note-:11-16">[16]</a> then the method evaluates the constraints in (<a href="#math_cb.4">cb.4</a>) to count how many correspondences actually agree with such a hypothesis (i.e., it computes the residual <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}}</annotation>

</semantics>

</math><img src="./2e00b1fd20efc5af3f0a1b597f9bfd5323bb3a86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:20.634ex; height:3.176ex;" alt="{\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}}" loading="lazy"> and compares it with the threshold <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy"> for each pair of measurements). The algorithm terminates either after it has found a consensus set that has enough correspondences, or after it has reached the total number of allowed iterations. RANSAC is highly efficient because the main computation of each iteration is carrying out the closed-form solution in Horn's method. However, RANSAC is non-deterministic and only works well in the low-outlier-ratio regime (e.g., below <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 50\%}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 50\%}</annotation>

</semantics>

</math><img src="./21af75c495d846b26a303c0d86b135d0488591d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.261ex; height:2.343ex;" alt="{\displaystyle 50\%}" loading="lazy">), because its runtime grows exponentially with respect to the outlier ratio.<a href="#cite_note-:0-20">[20]</a>

To fill the gap between the fast but inexact RANSAC scheme and the exact but exhaustive BnB optimization, recent researches have developed deterministic approximate methods to solve consensus maximization.<a href="#cite_note-:1-21">[21]</a><a href="#cite_note-:2-22">[22]</a><a href="#cite_note-27">[27]</a><a href="#cite_note-:3-23">[23]</a>

<div class="mw-heading mw-heading4"><h4 id="Outlier_removal">Outlier removal</h4></div>

Outlier removal methods seek to pre-process the set of highly corrupted correspondences before estimating the spatial transformation. The motivation of outlier removal is to significantly reduce the number of outlier correspondences, while maintaining inlier correspondences, so that optimization over the transformation becomes easier and more efficient (e.g., RANSAC works poorly when the outlier ratio is above <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 95\%}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 95\%}</annotation>

</semantics>

</math><img src="./38c9a021d5d9cf23f5453ada8675575253243554.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.261ex; height:2.343ex;" alt="{\displaystyle 95\%}" loading="lazy"> but performs quite well when outlier ratio is below <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 50\%}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 50\%}</annotation>

</semantics>

</math><img src="./21af75c495d846b26a303c0d86b135d0488591d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.261ex; height:2.343ex;" alt="{\displaystyle 50\%}" loading="lazy">).

Parra et al. have proposed a method called Guaranteed Outlier Removal (GORE) that uses geometric constraints to prune outlier correspondences while guaranteeing to preserve inlier correspondences.<a href="#cite_note-:0-20">[20]</a> GORE has been shown to be able to drastically reduce the outlier ratio, which can significantly boost the performance of consensus maximization using RANSAC or BnB. Yang and Carlone have proposed to build pairwise translation-and-rotation-invariant measurements (TRIMs) from the original set of measurements and embed TRIMs as the edges of a <a href="Graph_theory" title="Graph theory">graph</a> whose nodes are the 3D points. Since inliers are pairwise consistent in terms of the scale, they must form a <a href="Clique" title="Clique">clique</a> within the graph. Therefore, using efficient algorithms for computing the <a href="Clique_problem" title="Clique problem">maximum clique</a> of a graph can find the inliers and effectively prune the outliers.<a href="#cite_note-:4-4">[4]</a> The maximum clique based outlier removal method is also shown to be quite useful in real-world point set registration problems.<a href="#cite_note-:5-19">[19]</a> Similar outlier removal ideas were also proposed by Parra et al..<a href="#cite_note-28">[28]</a>

<div class="mw-heading mw-heading4"><h4 id="M-estimation">M-estimation</h4></div>

<a href="M-estimation" class="mw-redirect" title="M-estimation">M-estimation</a> replaces the least squares objective function in (<a href="#math_cb.2">cb.2</a>) with a robust cost function that is less sensitive to outliers. Formally, M-estimation seeks to solve the following problem:<table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\rho \left({\frac {1}{\sigma _{i}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}\right)}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\rho \left({\frac {1}{\sigma _{i}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}\right)}</annotation>

</semantics>

</math><img src="./9d4f4c91dfbcaa8641e040f5f5771dc9b2fac245.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:58.29ex; height:7.343ex;" alt="{\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\rho \left({\frac {1}{\sigma _{i}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}\right)}" loading="lazy"></td> <td></td> <td class="nowrap">cb.5</td></tr></tbody></table>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (\cdot )}</annotation>

</semantics>

</math><img src="./eebaff72613b0801efbe28c006f01f785415430e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.658ex; height:2.843ex;" alt="{\displaystyle \rho (\cdot )}" loading="lazy"> represents the choice of the robust cost function. Note that choosing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (x)=x^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (x)=x^{2}}</annotation>

</semantics>

</math><img src="./4e0df9fc8a361404c1d7be77ea8b97e8fd2a5787.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.823ex; height:3.176ex;" alt="{\displaystyle \rho (x)=x^{2}}" loading="lazy"> recovers the least squares estimation in (<a href="#math_cb.2">cb.2</a>). Popular robust cost functions include <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy">-norm loss, <a href="Huber_loss" title="Huber loss">Huber loss</a>,<a href="#cite_note-29">[29]</a> Geman-McClure loss<a href="#cite_note-:7-30">[30]</a> and <a href="Trimmed_estimator" title="Trimmed estimator">truncated least squares loss</a>.<a href="#cite_note-:5-19">[19]</a><a href="#cite_note-:6-8">[8]</a><a href="#cite_note-:4-4">[4]</a> M-estimation has been one of the most popular paradigms for robust estimation in robotics and computer vision.<a href="#cite_note-31">[31]</a><a href="#cite_note-32">[32]</a> Because robust objective functions are typically non-convex (e.g., the truncated least squares loss v.s. the least squares loss), algorithms for solving the non-convex M-estimation are typically based on <a href="Mathematical_optimization" title="Mathematical optimization">local optimization</a>, where first an initial guess is provided, following by iterative refinements of the transformation to keep decreasing the objective function. Local optimization tends to work well when the initial guess is close to the global minimum, but it is also prone to get stuck in local minima if provided with poor initialization.

<div class="mw-heading mw-heading4"><h4 id="Graduated_non-convexity">Graduated non-convexity</h4></div>

Graduated non-convexity (GNC) is a general-purpose framework for solving non-convex optimization problems without initialization. It has achieved success in early vision and machine learning applications.<a href="#cite_note-:8-33">[33]</a><a href="#cite_note-:9-34">[34]</a> The key idea behind GNC is to solve the hard non-convex problem by starting from an easy convex problem. Specifically, for a given robust cost function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (\cdot )}</annotation>

</semantics>

</math><img src="./eebaff72613b0801efbe28c006f01f785415430e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.658ex; height:2.843ex;" alt="{\displaystyle \rho (\cdot )}" loading="lazy">, one can construct a surrogate function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho _{\mu }(\cdot )}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho _{\mu }(\cdot )}</annotation>

</semantics>

</math><img src="./eb18099e6e0355de639dc0cb833f5be52a5962e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.881ex; height:3.009ex;" alt="{\displaystyle \rho _{\mu }(\cdot )}" loading="lazy"> with a hyper-parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy">, tuning which can gradually increase the non-convexity of the surrogate function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho _{\mu }(\cdot )}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho _{\mu }(\cdot )}</annotation>

</semantics>

</math><img src="./eb18099e6e0355de639dc0cb833f5be52a5962e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.881ex; height:3.009ex;" alt="{\displaystyle \rho _{\mu }(\cdot )}" loading="lazy"> until it converges to the target function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (\cdot )}</annotation>

</semantics>

</math><img src="./eebaff72613b0801efbe28c006f01f785415430e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.658ex; height:2.843ex;" alt="{\displaystyle \rho (\cdot )}" loading="lazy">.<a href="#cite_note-:9-34">[34]</a><a href="#cite_note-:10-35">[35]</a> Therefore, at each level of the hyper-parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy">, the following optimization is solved:<table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l_{\mu }^{\star },R_{\mu }^{\star },t_{\mu }^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\rho _{\mu }\left({\frac {1}{\sigma _{i}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}\right)}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l_{\mu }^{\star },R_{\mu }^{\star },t_{\mu }^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\rho _{\mu }\left({\frac {1}{\sigma _{i}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}\right)}</annotation>

</semantics>

</math><img src="./008d96da2071bbd585440d3fe017b6fc562887fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:60.021ex; height:7.343ex;" alt="{\displaystyle l_{\mu }^{\star },R_{\mu }^{\star },t_{\mu }^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\rho _{\mu }\left({\frac {1}{\sigma _{i}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}\right)}" loading="lazy"></td> <td></td> <td class="nowrap">cb.6</td></tr></tbody></table>Black and Rangarajan proved that the objective function of each optimization (<a href="#math_cb.6">cb.6</a>) can be dualized into a sum of <a href="Weighted_least_squares" title="Weighted least squares">weighted least squares</a> and a so-called outlier process function on the weights that determine the confidence of the optimization in each pair of measurements.<a href="#cite_note-:8-33">[33]</a> Using Black-Rangarajan duality and GNC tailored for the Geman-McClure function, Zhou et al. developed the fast global registration algorithm that is robust against about <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 80\%}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 80\%}</annotation>

</semantics>

</math><img src="./e1157809dd293a561e03d75d14f017c6697d6c1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.261ex; height:2.343ex;" alt="{\displaystyle 80\%}" loading="lazy"> outliers in the correspondences.<a href="#cite_note-:7-30">[30]</a> More recently, Yang et al. showed that the joint use of GNC (tailored to the Geman-McClure function and the truncated least squares function) and Black-Rangarajan duality can lead to a general-purpose solver for robust registration problems, including point clouds and mesh registration.<a href="#cite_note-:10-35">[35]</a>

<div class="mw-heading mw-heading4"><h4 id="Certifiably_robust_registration">Certifiably robust registration</h4></div>

Almost none of the robust registration algorithms mentioned above (except the BnB algorithm that runs in exponential-time in the worst case) comes with performance guarantees, which means that these algorithms can return completely incorrect estimates without notice. Therefore, these algorithms are undesirable for safety-critical applications like autonomous driving.

Very recently, Yang et al. has developed the first certifiably robust registration algorithm, named Truncated least squares Estimation And SEmidefinite Relaxation (TEASER).<a href="#cite_note-:5-19">[19]</a> For point cloud registration, TEASER not only outputs an estimate of the transformation, but also quantifies the optimality of the given estimate. TEASER adopts the following truncated least squares (TLS) estimator:<table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\min \left({\frac {1}{\sigma _{i}^{2}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}^{2},{\bar {c}}^{2}\right)}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<mfrac>

</mrow>

</mrow>

</msubsup>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\min \left({\frac {1}{\sigma _{i}^{2}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}^{2},{\bar {c}}^{2}\right)}</annotation>

</semantics>

</math><img src="./4ca1f497e55a0b3bdd272941d5b9cc5a3bbd2097.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:64.861ex; height:7.509ex;" alt="{\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3}}\sum _{i=1}^{N}\min \left({\frac {1}{\sigma _{i}^{2}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}^{2},{\bar {c}}^{2}\right)}" loading="lazy"></td> <td></td> <td class="nowrap">cb.7</td></tr></tbody></table>which is obtained by choosing the TLS robust cost function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (x)=\min(x^{2},{\bar {c}}^{2})}">

<msup>

</mrow>

</msup>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (x)=\min(x^{2},{\bar {c}}^{2})}</annotation>

</semantics>

</math><img src="./99f264b77c679bfd424d29e4ec93c1eff169282a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.888ex; height:3.176ex;" alt="{\displaystyle \rho (x)=\min(x^{2},{\bar {c}}^{2})}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\bar {c}}^{2}}">

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\bar {c}}^{2}}</annotation>

</semantics>

</math><img src="./5db843047cf5984accba1b378d2f5e8163eedc64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.346ex; height:2.676ex;" alt="{\displaystyle {\bar {c}}^{2}}" loading="lazy">is a pre-defined constant that determines the maximum allowed residuals to be considered inliers. The TLS objective function has the property that for inlier correspondences (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}<{\bar {c}}^{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}<{\bar {c}}^{2}}</annotation>

</semantics>

</math><img src="./f14b1fb5e2e4415ab61d8689472f9a903d298c12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:26.079ex; height:3.343ex;" alt="{\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}<{\bar {c}}^{2}}" loading="lazy">), the usual least square penalty is applied; while for outlier correspondences (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}>{\bar {c}}^{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}>{\bar {c}}^{2}}</annotation>

</semantics>

</math><img src="./e1d970b5394de0d1264c0c3f139357d7cdb77102.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:26.079ex; height:3.343ex;" alt="{\displaystyle \Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}>{\bar {c}}^{2}}" loading="lazy">), no penalty is applied and the outliers are discarded. If the TLS optimization (<a href="#math_cb.7">cb.7</a>) is solved to global optimality, then it is equivalent to running Horn's method on only the inlier correspondences.

However, solving (<a href="#math_cb.7">cb.7</a>) is quite challenging due to its combinatorial nature. TEASER solves (<a href="#math_cb.7">cb.7</a>) as follows : (i) It builds invariant measurements such that the estimation of scale, rotation and translation can be decoupled and solved separately, a strategy that is inspired by the original Horn's method; (ii) The same TLS estimation is applied for each of the three sub-problems, where the scale TLS problem can be solved exactly using an algorithm called adaptive voting, the rotation TLS problem can relaxed to a <a href="Semidefinite_programming" title="Semidefinite programming">semidefinite program</a> (SDP) where the relaxation is exact in practice,<a href="#cite_note-:6-8">[8]</a> even with large amount of outliers; the translation TLS problem can solved using component-wise adaptive voting. A fast implementation leveraging GNC is <a rel="nofollow" class="external text" href="https://github.com/MIT-SPARK/TEASER-plusplus">open-sourced here</a>. In practice, TEASER can tolerate more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 99\%}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 99\%}</annotation>

</semantics>

</math><img src="./ae56409666a51ff2cfceedc41f825bd2dfd84dd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.261ex; height:2.343ex;" alt="{\displaystyle 99\%}" loading="lazy"> outlier correspondences and runs in milliseconds.

In addition to developing TEASER, Yang et al. also prove that, under some mild conditions on the point cloud data, TEASER's estimated transformation has bounded errors from the ground-truth transformation.<a href="#cite_note-:5-19">[19]</a>

<div class="mw-heading mw-heading2"><h2 id="Simultaneous_pose_and_correspondence_registration">Simultaneous pose and correspondence registration</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Iterative_closest_point">Iterative closest point</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Iterative_closest_point" title="Iterative closest point">Iterative closest point</a></div>

The <a href="Iterative_closest_point" title="Iterative closest point">iterative closest point</a> (ICP) algorithm was introduced by Besl and McKay.<a href="#cite_note-icpbesl-36">[36]</a>

The algorithm performs rigid registration in an iterative fashion by alternating in (i) given the transformation, finding <a href="Nearest_neighbor_search" title="Nearest neighbor search">the closest point</a> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy"> for every point in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy">; and (ii) given the correspondences, finding the best rigid transformation by solving the <a href="Least_squares" title="Least squares">least squares</a> problem (<a href="#math_cb.2">cb.2</a>). As such, it works best if the initial pose of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> is sufficiently close to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy">. In <a href="Pseudocode" title="Pseudocode">pseudocode</a>, the basic algorithm is implemented as follows:

<pre>algorithm ICP(M, S)

θ := θ0

while not registered:

X := ∅

for mi ∊ T(M, θ):

ŝi := closest point in S to mi

X := X + ⟨mi, ŝi⟩

θ := least_squares(X)

return θ

</pre>

Here, the function <code>least_squares</code> performs <a href="Least_squares" title="Least squares">least squares</a> optimization to minimize the distance in each of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle m_{i},{\hat {s}}_{i}\rangle }">

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle m_{i},{\hat {s}}_{i}\rangle }</annotation>

</semantics>

</math><img src="./9ef65e391d6da7ab9f26c02dd1d67eb2b218b880.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.775ex; height:2.843ex;" alt="{\displaystyle \langle m_{i},{\hat {s}}_{i}\rangle }" loading="lazy"> pairs, using the closed-form solutions by Horn<a href="#cite_note-:11-16">[16]</a> and Arun.<a href="#cite_note-:12-17">[17]</a>

Because the <a href="Loss_function" title="Loss function">cost function</a> of registration depends on finding the closest point in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy"> to every point in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy">, it can change as the algorithm is running. As such, it is difficult to prove that ICP will in fact converge exactly to the local optimum.<a href="#cite_note-kctsin-37">[37]</a> In fact, empirically, ICP and EM-ICP do not converge to the local minimum of the cost function.<a href="#cite_note-kctsin-37">[37]</a> Nonetheless, because ICP is intuitive to understand and straightforward to implement, it remains the most commonly used point set registration algorithm.<a href="#cite_note-kctsin-37">[37]</a> Many variants of ICP have been proposed, affecting all phases of the algorithm from the selection and matching of points to the minimization strategy.<a href="#cite_note-cpdmyronenko2-13">[13]</a><a href="#cite_note-fasticp-38">[38]</a>

For example, the <a href="Expectation_maximization" class="mw-redirect" title="Expectation maximization">expectation maximization</a> algorithm is applied to the ICP algorithm to form the EM-ICP method, and the <a href="Levenberg-Marquardt_algorithm" class="mw-redirect" title="Levenberg-Marquardt algorithm">Levenberg-Marquardt algorithm</a> is applied to the ICP algorithm to form the LM-ICP method.<a href="#cite_note-lmfitzgibbon-12">[12]</a>

<div class="mw-heading mw-heading3"><h3 id="Robust_point_matching">Robust point matching</h3></div>

Robust point matching (RPM) was introduced by Gold et al.<a href="#cite_note-rpmgold-39">[39]</a> The method performs registration using <a href="Deterministic_annealing" class="mw-redirect" title="Deterministic annealing">deterministic annealing</a> and soft assignment of correspondences between point sets. Whereas in ICP the correspondence generated by the nearest-neighbour heuristic is binary, RPM uses a soft correspondence where the correspondence between any two points can be anywhere from 0 to 1, although it ultimately converges to either 0 or 1. The correspondences found in RPM is always one-to-one, which is not always the case in ICP.<a href="#cite_note-tpsrpmchui-14">[14]</a> Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>

</semantics>

</math><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"> be the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">th point in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{j}}</annotation>

</semantics>

</math><img src="./c6a350c64508aef872d4e72ee677746ef7a20f72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2ex; height:2.343ex;" alt="{\displaystyle s_{j}}" loading="lazy"> be the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy">th point in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy">. The match matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {\mu } }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {\mu } }</annotation>

</semantics>

</math><img src="./e407f1e8e83fffbed7e61f4112b7eef6b22b9e67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mathbf {\mu } }" loading="lazy"> is defined as such:

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>if point </mtext>

</mrow>

<msub>

</mrow>

</msub>

<mtext> corresponds to point </mtext>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>otherwise</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{ij}={\begin{cases}1&{\text{if point }}m_{i}{\text{ corresponds to point }}s_{j}\\0&{\text{otherwise}}\end{cases}}}</annotation>

</semantics>

</math><img src="./05d0b7507bd5202296175666ba7c11adba9d1802.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:46.228ex; height:6.176ex;" alt="{\displaystyle \mu _{ij}={\begin{cases}1&{\text{if point }}m_{i}{\text{ corresponds to point }}s_{j}\\0&{\text{otherwise}}\end{cases}}}" loading="lazy"></td> <td></td> <td class="nowrap">rpm.1</td></tr></tbody></table>

The problem is then defined as: Given two point sets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy"> find the <a href="Affine_transformation" title="Affine transformation">Affine transformation</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> and the match matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {\mu } }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {\mu } }</annotation>

</semantics>

</math><img src="./e407f1e8e83fffbed7e61f4112b7eef6b22b9e67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mathbf {\mu } }" loading="lazy"> that best relates them.<a href="#cite_note-rpmgold-39">[39]</a> Knowing the optimal transformation makes it easy to determine the match matrix, and vice versa. However, the RPM algorithm determines both simultaneously. The transformation may be decomposed into a translation vector and a transformation matrix:

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(m)=\mathbf {A} m+\mathbf {t} }</annotation>

</semantics>

</math><img src="./9bc6a57a81465b7a22e0e6f08470b111d96e3306.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.524ex; height:2.843ex;" alt="{\displaystyle T(m)=\mathbf {A} m+\mathbf {t} }" loading="lazy"></dd></dl>

The matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {A} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {A} }</annotation>

</semantics>

</math><img src="./0795cc96c75d81520a120482662b90f024c9a1a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.019ex; height:2.176ex;" alt="{\displaystyle \mathbf {A} }" loading="lazy"> in 2D is composed of four separate parameters <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lbrace a,\theta ,b,c\rbrace }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lbrace a,\theta ,b,c\rbrace }</annotation>

</semantics>

</math><img src="./f8eafffa516ae0198f8652fa2249b386326f3237.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.751ex; height:2.843ex;" alt="{\displaystyle \lbrace a,\theta ,b,c\rbrace }" loading="lazy">, which are scale, rotation, and the vertical and horizontal shear components respectively. The cost function is then:

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {cost} =\sum _{j=1}^{N}\sum _{i=1}^{M}\mu _{ij}\lVert s_{j}-\mathbf {t} -\mathbf {A} m_{i}\rVert ^{2}+g(\mathbf {A} )-\alpha \sum _{j=1}^{N}\sum _{i=1}^{M}\mu _{ij}}</annotation>

</semantics>

</math><img src="./2912b45455e5e568d4b7917016245ab30cdcb3ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:57.3ex; height:7.676ex;" alt="{\displaystyle \operatorname {cost} =\sum _{j=1}^{N}\sum _{i=1}^{M}\mu _{ij}\lVert s_{j}-\mathbf {t} -\mathbf {A} m_{i}\rVert ^{2}+g(\mathbf {A} )-\alpha \sum _{j=1}^{N}\sum _{i=1}^{M}\mu _{ij}}" loading="lazy"></td> <td></td> <td class="nowrap">rpm.2</td></tr></tbody></table>

subject to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}\leq 1}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}\leq 1}</annotation>

</semantics>

</math><img src="./85f39bba87685bc12c2e9bf37eb8239610427ff9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.099ex; height:3.509ex;" alt="{\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}\leq 1}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}\leq 1}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}\leq 1}</annotation>

</semantics>

</math><img src="./2e6a34158dab482a0ecf81ea529ec8b3713952eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:16.054ex; height:3.843ex;" alt="{\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}\leq 1}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \forall ij~\mu _{ij}\in \lbrace 0,1\rbrace }">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \forall ij~\mu _{ij}\in \lbrace 0,1\rbrace }</annotation>

</semantics>

</math><img src="./9a99a2a304192fc6ce2c602023a34144f2563dcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.037ex; height:3.009ex;" alt="{\textstyle \forall ij~\mu _{ij}\in \lbrace 0,1\rbrace }" loading="lazy">. The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> term biases the objective towards stronger correlation by decreasing the cost if the match matrix has more ones in it. The function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(\mathbf {A} )}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(\mathbf {A} )}</annotation>

</semantics>

</math><img src="./0c354b0d1c5a41217a3e15cc66083fcb7fb09cd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.945ex; height:2.843ex;" alt="{\displaystyle g(\mathbf {A} )}" loading="lazy"> serves to regularize the Affine transformation by penalizing large values of the scale and shear components:

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(\mathbf {A} (a,\theta ,b,c))=\gamma (a^{2}+b^{2}+c^{2})}</annotation>

</semantics>

</math><img src="./691be2fb9e69dbbffe21c7ca7a49160c2a745527.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.428ex; height:3.176ex;" alt="{\displaystyle g(\mathbf {A} (a,\theta ,b,c))=\gamma (a^{2}+b^{2}+c^{2})}" loading="lazy"></dd></dl>

for some regularization parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma }</annotation>

</semantics>

</math><img src="./a223c880b0ce3da8f64ee33c4f0010beee400b1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.262ex; height:2.176ex;" alt="{\displaystyle \gamma }" loading="lazy">.

The RPM method optimizes the cost function using the Softassign algorithm. The 1D case will be derived here. Given a set of variables <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lbrace Q_{j}\rbrace }">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lbrace Q_{j}\rbrace }</annotation>

</semantics>

</math><img src="./35bb5192ed7d291e904f19dee2d9236fe51b5293.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.073ex; height:3.009ex;" alt="{\displaystyle \lbrace Q_{j}\rbrace }" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{j}\in \mathbb {R} ^{1}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{j}\in \mathbb {R} ^{1}}</annotation>

</semantics>

</math><img src="./802aa2950217a1b4cbd2dbf76b536d3923fa4709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.321ex; height:3.343ex;" alt="{\displaystyle Q_{j}\in \mathbb {R} ^{1}}" loading="lazy">. A variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{j}}</annotation>

</semantics>

</math><img src="./4b2800dcde32ff75ad8aecdf9c4c4e2d7fad58db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.311ex; height:2.343ex;" alt="{\displaystyle \mu _{j}}" loading="lazy"> is associated with each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{j}}</annotation>

</semantics>

</math><img src="./5db0ad37e47589c5a9f270ca9c06affdacd6c66f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.748ex; height:2.843ex;" alt="{\displaystyle Q_{j}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \sum _{j=1}^{J}\mu _{j}=1}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \sum _{j=1}^{J}\mu _{j}=1}</annotation>

</semantics>

</math><img src="./b73be867e86f74de717a29464651654cad07f8bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:12.423ex; height:3.843ex;" alt="{\textstyle \sum _{j=1}^{J}\mu _{j}=1}" loading="lazy">. The goal is to find <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {\mu } }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {\mu } }</annotation>

</semantics>

</math><img src="./e407f1e8e83fffbed7e61f4112b7eef6b22b9e67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mathbf {\mu } }" loading="lazy"> that maximizes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}</annotation>

</semantics>

</math><img src="./8133f1a5058f8123d49988959466413f4dc04394.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:10.911ex; height:3.843ex;" alt="{\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}" loading="lazy">. This can be formulated as a continuous problem by introducing a control parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta >0}</annotation>

</semantics>

</math><img src="./4a87dc52878418173659e6d0ff8e77ab2897eac9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.593ex; height:2.509ex;" alt="{\displaystyle \beta >0}" loading="lazy">. In the <a href="Deterministic_annealing" class="mw-redirect" title="Deterministic annealing">deterministic annealing</a> method, the control parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta }</annotation>

</semantics>

</math><img src="./7ed48a5e36207156fb792fa79d29925d2f7901e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.332ex; height:2.509ex;" alt="{\displaystyle \beta }" loading="lazy"> is slowly increased as the algorithm runs. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {\mu } }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {\mu } }</annotation>

</semantics>

</math><img src="./e407f1e8e83fffbed7e61f4112b7eef6b22b9e67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mathbf {\mu } }" loading="lazy"> be:

<msub>

<mover>

</mover>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

<mover>

</mover>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{\hat {j}}={\frac {\exp {(\beta Q_{\hat {j}})}}{\sum _{j=1}^{J}\exp {(\beta Q_{j})}}}}</annotation>

</semantics>

</math><img src="./8f37bf2f5e51f71e3d4bcb9cd7089dc16ce76b30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:22.071ex; height:7.843ex;" alt="{\displaystyle \mu _{\hat {j}}={\frac {\exp {(\beta Q_{\hat {j}})}}{\sum _{j=1}^{J}\exp {(\beta Q_{j})}}}}" loading="lazy"></td> <td></td> <td class="nowrap">rpm.3</td></tr></tbody></table>

this is known as the <a href="Softmax_function" title="Softmax function">softmax function</a>. As <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta }</annotation>

</semantics>

</math><img src="./7ed48a5e36207156fb792fa79d29925d2f7901e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.332ex; height:2.509ex;" alt="{\displaystyle \beta }" loading="lazy"> increases, it approaches a binary value as desired in Equation (<a href="#math_rpm.1">rpm.1</a>). The problem may now be generalized to the 2D case, where instead of maximizing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}</annotation>

</semantics>

</math><img src="./8133f1a5058f8123d49988959466413f4dc04394.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:10.911ex; height:3.843ex;" alt="{\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}" loading="lazy">, the following is maximized:

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(\mu )=\sum _{j=1}^{N}\sum _{i=0}^{M}\mu _{ij}Q_{ij}}</annotation>

</semantics>

</math><img src="./51d68b237803e3d73af277d2d51f7d9e708939af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:21.764ex; height:7.676ex;" alt="{\displaystyle E(\mu )=\sum _{j=1}^{N}\sum _{i=0}^{M}\mu _{ij}Q_{ij}}" loading="lazy"></td> <td></td> <td class="nowrap">rpm.4</td></tr></tbody></table>

where

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{ij}=-(\lVert s_{j}-\mathbf {t} -\mathbf {A} m_{i}\rVert ^{2}-\alpha )=-{\frac {\partial \operatorname {cost} }{\partial \mu _{ij}}}}</annotation>

</semantics>

</math><img src="./349308e587b85b292866336d54fc830bf9479418.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:42.782ex; height:6.176ex;" alt="{\displaystyle Q_{ij}=-(\lVert s_{j}-\mathbf {t} -\mathbf {A} m_{i}\rVert ^{2}-\alpha )=-{\frac {\partial \operatorname {cost} }{\partial \mu _{ij}}}}" loading="lazy"></dd></dl>

This is straightforward, except that now the constraints on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"> are <a href="Doubly_stochastic_matrix" title="Doubly stochastic matrix">doubly stochastic matrix</a> constraints: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}=1}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}=1}</annotation>

</semantics>

</math><img src="./d1b3199276bb6fd5a189cb6a5fdbe5f4bd6490b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.099ex; height:3.509ex;" alt="{\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}=1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}=1}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}=1}</annotation>

</semantics>

</math><img src="./e07704abe1296c11262f24c5acf6fd424fccf84c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:16.054ex; height:3.843ex;" alt="{\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}=1}" loading="lazy">. As such the denominator from Equation (<a href="#math_rpm.3">rpm.3</a>) cannot be expressed for the 2D case simply. To satisfy the constraints, it is possible to use a result due to Sinkhorn,<a href="#cite_note-rpmgold-39">[39]</a> which states that a doubly stochastic matrix is obtained from any square matrix with all positive entries by the iterative process of alternating row and column normalizations. Thus the algorithm is written as such:<a href="#cite_note-rpmgold-39">[39]</a>

<pre>algorithm RPM2D<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ({\mathcal {M}},{\mathcal {S}})}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ({\mathcal {M}},{\mathcal {S}})}</annotation>

</semantics>

</math><img src="./a3274d9795d894cf4f995a61b88ee34e40a6dc7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.126ex; height:2.843ex;" alt="{\displaystyle ({\mathcal {M}},{\mathcal {S}})}" loading="lazy">

t := 0

a, θ b, c := 0

β := β0

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mu }}_{ij}:=1+\epsilon }</annotation>

</semantics>

</math><img src="./c599955905e0c32a51ec3332183cce7697d70a55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.571ex; height:3.009ex;" alt="{\displaystyle {\hat {\mu }}_{ij}:=1+\epsilon }" loading="lazy">

while β < βf:

while μ has not converged:

// update correspondence parameters by softassign

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{ij}:=-{\frac {\partial \operatorname {cost} }{\partial \mu _{ij}}}}</annotation>

</semantics>

</math><img src="./11b78e9a28bc8d36a268e4fdecf16447cfabb6b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:15.426ex; height:6.176ex;" alt="{\displaystyle Q_{ij}:=-{\frac {\partial \operatorname {cost} }{\partial \mu _{ij}}}}" loading="lazy">

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{ij}^{0}:=\exp(\beta Q_{ij})}</annotation>

</semantics>

</math><img src="./32283d63f8e261ac2b0dd05f94bb84e3b7eb7e8f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:16.633ex; height:3.509ex;" alt="{\displaystyle \mu _{ij}^{0}:=\exp(\beta Q_{ij})}" loading="lazy">

// apply Sinkhorn's method

while <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {\mu }}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mu }}}</annotation>

</semantics>

</math><img src="./bd4ffaa21cda12fe3da1cfb384b7b22094fefb5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.676ex;" alt="{\displaystyle {\hat {\mu }}}" loading="lazy"> has not converged:

// update <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {\mu }}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mu }}}</annotation>

</semantics>

</math><img src="./bd4ffaa21cda12fe3da1cfb384b7b22094fefb5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.676ex;" alt="{\displaystyle {\hat {\mu }}}" loading="lazy"> by normalizing across all rows:

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<mfrac>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<mrow>

</mrow>

</mrow>

</munderover>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mu }}_{ij}^{1}:={\frac {{\hat {\mu }}_{ij}^{0}}{\sum _{i=1}^{M+1}{\hat {\mu }}_{ij}^{0}}}}</annotation>

</semantics>

</math><img src="./dee595afb4ec7ccbc556099c7deb357870511b6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:17.24ex; height:8.009ex;" alt="{\displaystyle {\hat {\mu }}_{ij}^{1}:={\frac {{\hat {\mu }}_{ij}^{0}}{\sum _{i=1}^{M+1}{\hat {\mu }}_{ij}^{0}}}}" loading="lazy">

// update <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {\mu }}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mu }}}</annotation>

</semantics>

</math><img src="./bd4ffaa21cda12fe3da1cfb384b7b22094fefb5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.676ex;" alt="{\displaystyle {\hat {\mu }}}" loading="lazy"> by normalizing across all columns:

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<mfrac>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

<mrow>

</mrow>

</mrow>

</munderover>

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mu }}_{ij}^{0}:={\frac {{\hat {\mu }}_{ij}^{1}}{\sum _{j=1}^{N+1}{\hat {\mu }}_{ij}^{1}}}}</annotation>

</semantics>

</math><img src="./ebe09ca4b592e3242d6dc496e95b6e07d570743a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:16.972ex; height:8.009ex;" alt="{\displaystyle {\hat {\mu }}_{ij}^{0}:={\frac {{\hat {\mu }}_{ij}^{1}}{\sum _{j=1}^{N+1}{\hat {\mu }}_{ij}^{1}}}}" loading="lazy">

// update pose parameters by coordinate descent

update θ using analytical solution

update t using analytical solution

update a, b, c using <a href="Newton's_method" title="Newton's method">Newton's method</a>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta :=\beta _{r}\beta }</annotation>

</semantics>

</math><img src="./4bf5e0c715071478da81bc5db0cefb6645cd78fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.699ex; height:2.509ex;" alt="{\displaystyle \beta :=\beta _{r}\beta }" loading="lazy">

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma :={\frac {\gamma }{\beta _{r}}}}</annotation>

</semantics>

</math><img src="./2a219e4a9568b1c02dfc84a6a2c43e0974801ea9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:8.133ex; height:5.343ex;" alt="{\displaystyle \gamma :={\frac {\gamma }{\beta _{r}}}}" loading="lazy">

return a, b, c, θ and t

</pre>

where the deterministic annealing control parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta }</annotation>

</semantics>

</math><img src="./7ed48a5e36207156fb792fa79d29925d2f7901e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.332ex; height:2.509ex;" alt="{\displaystyle \beta }" loading="lazy"> is initially set to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta _{0}}</annotation>

</semantics>

</math><img src="./40b42f71f244103a8fca3c76885c7580a92831c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.37ex; height:2.509ex;" alt="{\displaystyle \beta _{0}}" loading="lazy"> and increases by factor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta _{r}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta _{r}}</annotation>

</semantics>

</math><img src="./77b1a896de1d384e97fc90d01614eb230059d58c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.29ex; height:2.509ex;" alt="{\displaystyle \beta _{r}}" loading="lazy"> until it reaches the maximum value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta _{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta _{f}}</annotation>

</semantics>

</math><img src="./1d4000652538ec46765d605398ac983b322aafec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.452ex; height:2.843ex;" alt="{\displaystyle \beta _{f}}" loading="lazy">. The summations in the normalization steps sum to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M+1}</annotation>

</semantics>

</math><img src="./03c0b0dc5ee6ec29023977ea04ad152977fcba18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.445ex; height:2.343ex;" alt="{\displaystyle M+1}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N+1}</annotation>

</semantics>

</math><img src="./fdf2b9cbfe9051fd4e7b50c8028866d497eac35b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.066ex; height:2.343ex;" alt="{\displaystyle N+1}" loading="lazy"> instead of just <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> because the constraints on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"> are inequalities. As such the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M+1}</annotation>

</semantics>

</math><img src="./03c0b0dc5ee6ec29023977ea04ad152977fcba18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.445ex; height:2.343ex;" alt="{\displaystyle M+1}" loading="lazy">th and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N+1}</annotation>

</semantics>

</math><img src="./fdf2b9cbfe9051fd4e7b50c8028866d497eac35b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.066ex; height:2.343ex;" alt="{\displaystyle N+1}" loading="lazy">th elements are <a href="Slack_variable" title="Slack variable">slack variables</a>.

The algorithm can also be extended for point sets in 3D or higher dimensions. The constraints on the correspondence matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {\mu } }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {\mu } }</annotation>

</semantics>

</math><img src="./e407f1e8e83fffbed7e61f4112b7eef6b22b9e67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mathbf {\mu } }" loading="lazy"> are the same in the 3D case as in the 2D case. Hence the structure of the algorithm remains unchanged, with the main difference being how the rotation and translation matrices are solved.<a href="#cite_note-rpmgold-39">[39]</a>

<div class="mw-heading mw-heading4"><h4 id="Thin_plate_spline_robust_point_matching">Thin plate spline robust point matching</h4></div>

The thin plate spline robust point matching (TPS-RPM) algorithm by Chui and Rangarajan augments the RPM method to perform non-rigid registration by parametrizing the transformation as a <a href="Thin_plate_spline" title="Thin plate spline">thin plate spline</a>.<a href="#cite_note-tpsrpmchui-14">[14]</a>

However, because the thin plate spline parametrization only exists in three dimensions, the method cannot be extended to problems involving four or more dimensions.

<div class="mw-heading mw-heading3"><h3 id="Kernel_correlation">Kernel correlation</h3></div>

The kernel correlation (KC) approach of point set registration was introduced by Tsin and Kanade.<a href="#cite_note-kctsin-37">[37]</a>

Compared with ICP, the KC algorithm is more robust against noisy data. Unlike ICP, where, for every model point, only the closest scene point is considered, here every scene point affects every model point.<a href="#cite_note-kctsin-37">[37]</a> As such this is a multiply-linked registration algorithm. For some <a href="Kernel_function" class="mw-redirect" title="Kernel function">kernel function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy">, the kernel correlation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle KC}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle KC}</annotation>

</semantics>

</math><img src="./f99fa1367fd99c87ae226c8a70f1d0af4bbb8621.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.832ex; height:2.176ex;" alt="{\displaystyle KC}" loading="lazy"> of two points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i},x_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i},x_{j}}</annotation>

</semantics>

</math><img src="./1cd4d8ff7cb1b6282ffbee7cdfebd612cf5fb146.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.403ex; height:2.343ex;" alt="{\displaystyle x_{i},x_{j}}" loading="lazy"> is defined thus:<a href="#cite_note-kctsin-37">[37]</a>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle KC(x_{i},x_{j})=\int K(x,x_{i})\cdot K(x,x_{j})dx}</annotation>

</semantics>

</math><img src="./c5f8e031dffacd806d782b4055959e07e6d2f577.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:37.795ex; height:5.676ex;" alt="{\displaystyle KC(x_{i},x_{j})=\int K(x,x_{i})\cdot K(x,x_{j})dx}" loading="lazy"></td> <td></td> <td class="nowrap">kc.1</td></tr></tbody></table>

The <a href="Kernel_(statistics)#In_non-parametric_statistics" title="Kernel (statistics)">kernel function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> chosen for point set registration is typically symmetric and non-negative kernel, similar to the ones used in the <a href="Parzen_window" class="mw-redirect" title="Parzen window">Parzen window</a> density estimation. The <a href="Gaussian_kernel" class="mw-redirect" title="Gaussian kernel">Gaussian kernel</a> typically used for its simplicity, although other ones like the <a href="Epanechnikov_kernel" class="mw-redirect" title="Epanechnikov kernel">Epanechnikov kernel</a> and the tricube kernel may be substituted.<a href="#cite_note-kctsin-37">[37]</a> The kernel correlation of an entire point set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {\chi }}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {\chi }}}</annotation>

</semantics>

</math><img src="./75dcc267cfc4d97096e4808fb93ef940aeebcdf3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.455ex; height:2.009ex;" alt="{\displaystyle {\mathcal {\chi }}}" loading="lazy"> is defined as the sum of the kernel correlations of every point in the set to every other point in the set:<a href="#cite_note-kctsin-37">[37]</a>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle KC({\mathcal {X}})=\sum _{i\neq j}KC(x_{i},x_{j})=2\sum _{i<j}KC(x_{i},x_{j})}</annotation>

</semantics>

</math><img src="./241b683493d3e4ab070e08eda3a0b14c4898df39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:44.836ex; height:6.009ex;" alt="{\displaystyle KC({\mathcal {X}})=\sum _{i\neq j}KC(x_{i},x_{j})=2\sum _{i<j}KC(x_{i},x_{j})}" loading="lazy"></td> <td></td> <td class="nowrap">kc.2</td></tr></tbody></table>

The logarithm of KC of a point set is proportional, within a constant factor, to the <a href="Entropy_(information_theory)" title="Entropy (information theory)">information entropy</a>. Observe that the KC is a measure of a "compactness" of the point set—trivially, if all points in the point set were at the same location, the KC would evaluate to a large value. The <a href="Loss_function" title="Loss function">cost function</a> of the point set registration algorithm for some transformation parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> is defined thus:

</mrow>

</mrow>

</mrow>

</munder>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )=-\sum _{m\in {\mathcal {M}}}\sum _{s\in {\mathcal {S}}}KC(s,T(m,\theta ))}</annotation>

</semantics>

</math><img src="./3f050178d15aef42046dfdcdbdcbb6a36f3c07dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:42.578ex; height:5.676ex;" alt="{\displaystyle \operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )=-\sum _{m\in {\mathcal {M}}}\sum _{s\in {\mathcal {S}}}KC(s,T(m,\theta ))}" loading="lazy"></td> <td></td> <td class="nowrap">kc.3</td></tr></tbody></table>

Some algebraic manipulation yields:

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle KC({\mathcal {S}}\cup T({\mathcal {M}},\theta ))=KC({\mathcal {S}})+KC(T({\mathcal {M}},\theta ))-2\operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )}</annotation>

</semantics>

</math><img src="./912308637f61bf49d46a98178b6fb0514079fca1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:62.808ex; height:2.843ex;" alt="{\displaystyle KC({\mathcal {S}}\cup T({\mathcal {M}},\theta ))=KC({\mathcal {S}})+KC(T({\mathcal {M}},\theta ))-2\operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )}" loading="lazy"></td> <td></td> <td class="nowrap">kc.4</td></tr></tbody></table>

The expression is simplified by observing that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle KC({\mathcal {S}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle KC({\mathcal {S}})}</annotation>

</semantics>

</math><img src="./cfc59cfec53c1fee6f14fea13e9f861e4728ba9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.134ex; height:2.843ex;" alt="{\displaystyle KC({\mathcal {S}})}" loading="lazy"> is independent of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy">. Furthermore, assuming rigid registration, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle KC(T({\mathcal {M}},\theta ))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle KC(T({\mathcal {M}},\theta ))}</annotation>

</semantics>

</math><img src="./a780ec5427dab3996d1b610eab6330d5bcc5b492.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle KC(T({\mathcal {M}},\theta ))}" loading="lazy"> is invariant when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> is changed because the Euclidean distance between every pair of points stays the same under <a href="Rigid_transformation" title="Rigid transformation">rigid transformation</a>. So the above equation may be rewritten as:

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle KC({\mathcal {S}}\cup T({\mathcal {M}},\theta ))=C-2\operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )}</annotation>

</semantics>

</math><img src="./586d1ba51af8c8924f6f1703b957f30089049154.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.598ex; height:2.843ex;" alt="{\displaystyle KC({\mathcal {S}}\cup T({\mathcal {M}},\theta ))=C-2\operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )}" loading="lazy"></td> <td></td> <td class="nowrap">kc.5</td></tr></tbody></table>

The <a href="Kernel_density_estimation" title="Kernel density estimation">kernel density estimates</a> are defined as:

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{\mathcal {M}}(x,\theta )={\frac {1}{M}}\sum _{m\in {\mathcal {M}}}K(x,T(m,\theta ))}</annotation>

</semantics>

</math><img src="./8caf355125bc062cedd23b856983ca4dada662bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:34.474ex; height:6.509ex;" alt="{\displaystyle P_{\mathcal {M}}(x,\theta )={\frac {1}{M}}\sum _{m\in {\mathcal {M}}}K(x,T(m,\theta ))}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{\mathcal {S}}(x)={\frac {1}{N}}\sum _{s\in {\mathcal {S}}}K(x,s)}</annotation>

</semantics>

</math><img src="./4369a73d542ecfdc8371a4260fa5d781513b20a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:23.375ex; height:6.509ex;" alt="{\displaystyle P_{\mathcal {S}}(x)={\frac {1}{N}}\sum _{s\in {\mathcal {S}}}K(x,s)}" loading="lazy"></dd></dl>

The cost function can then be shown to be the correlation of the two kernel density estimates:

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )=-N^{2}\int _{x}P_{\mathcal {M}}\cdot P_{\mathcal {S}}~dx}</annotation>

</semantics>

</math><img src="./3a49c95679d8b3b05c43bb8c7f5e28a3289c0332.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:35.872ex; height:5.676ex;" alt="{\displaystyle \operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )=-N^{2}\int _{x}P_{\mathcal {M}}\cdot P_{\mathcal {S}}~dx}" loading="lazy"></td> <td></td> <td class="nowrap">kc.6</td></tr></tbody></table>

Having established the <a href="Loss_function" title="Loss function">cost function</a>, the algorithm simply uses <a href="Gradient_descent" title="Gradient descent">gradient descent</a> to find the optimal transformation. It is computationally expensive to compute the cost function from scratch on every iteration, so a discrete version of the cost function Equation (<a href="#math_kc.6">kc.6</a>) is used. The kernel density estimates <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{\mathcal {M}},P_{\mathcal {S}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{\mathcal {M}},P_{\mathcal {S}}}</annotation>

</semantics>

</math><img src="./c0b0be463ef41d8f925196cb9c860c3a79e20c3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.511ex; height:2.509ex;" alt="{\displaystyle P_{\mathcal {M}},P_{\mathcal {S}}}" loading="lazy"> can be evaluated at grid points and stored in a <a href="Lookup_table" title="Lookup table">lookup table</a>. Unlike the ICP and related methods, it is not necessary to find the nearest neighbour, which allows the KC algorithm to be comparatively simple in implementation.

Compared to ICP and EM-ICP for noisy 2D and 3D point sets, the KC algorithm is less sensitive to noise and results in correct registration more often.<a href="#cite_note-kctsin-37">[37]</a>

<div class="mw-heading mw-heading4"><h4 id="Gaussian_mixture_model">Gaussian mixture model</h4></div>

The kernel density estimates are sums of Gaussians and may therefore be represented as <a href="Gaussian_mixture_model" class="mw-redirect" title="Gaussian mixture model">Gaussian mixture models</a> (GMM).<a href="#cite_note-gmmjian2-40">[40]</a> Jian and Vemuri use the GMM version of the KC registration algorithm to perform non-rigid registration parametrized by <a href="Thin_plate_spline" title="Thin plate spline">thin plate splines</a>.

<div class="mw-heading mw-heading3"><h3 id="Coherent_point_drift">Coherent point drift</h3></div>

Coherent point drift (CPD) was introduced by Myronenko and Song.<a href="#cite_note-cpdmyronenko2-13">[13]</a><a href="#cite_note-cpdmyronenko-41">[41]</a>

The algorithm takes a probabilistic approach to aligning point sets, similar to the GMM KC method. Unlike earlier approaches to non-rigid registration which assume a <a href="Thin_plate_spline" title="Thin plate spline">thin plate spline</a> transformation model, CPD is agnostic with regard to the transformation model used. The point set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> represents the <a href="Gaussian_mixture_model" class="mw-redirect" title="Gaussian mixture model">Gaussian mixture model</a> (GMM) centroids. When the two point sets are optimally aligned, the correspondence is the maximum of the GMM <a href="Posterior_probability" title="Posterior probability">posterior probability</a> for a given data point. To preserve the topological structure of the point sets, the GMM centroids are forced to move coherently as a group. The <a href="Expectation_maximization" class="mw-redirect" title="Expectation maximization">expectation maximization</a> algorithm is used to optimize the cost function.<a href="#cite_note-cpdmyronenko2-13">[13]</a>

Let there be M points in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> and N points in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy">. The GMM <a href="Probability_density_function" title="Probability density function">probability density function</a> for a point s is:

</mrow>

</mrow>

</munderover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(s)=\sum _{i=1}^{M+1}P(i)p(s|i)}</annotation>

</semantics>

</math><img src="./ad0c57ecae6da46281c9705c4f9a29b117a5ff96.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; margin-left: -0.089ex; width:21.347ex; height:7.343ex;" alt="{\displaystyle p(s)=\sum _{i=1}^{M+1}P(i)p(s|i)}" loading="lazy"></td> <td></td> <td class="nowrap">cpd.1</td></tr></tbody></table>

where, in D dimensions, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(s|i)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(s|i)}</annotation>

</semantics>

</math><img src="./a05d52874a44c24682af2033a0b087b9e44965bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:5.608ex; height:2.843ex;" alt="{\displaystyle p(s|i)}" loading="lazy"> is the <a href="Gaussian_distribution" class="mw-redirect" title="Gaussian distribution">Gaussian distribution</a> centered on point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}\in {\mathcal {M}}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{i}\in {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./67fcbb6d23f216b2ea200356d25c6f63fef64986.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.471ex; height:2.509ex;" alt="{\displaystyle m_{i}\in {\mathcal {M}}}" loading="lazy">.

</mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(s|i)={\frac {1}{(2\pi \sigma ^{2})^{D/2}}}\exp {\left(-{\frac {\lVert s-m_{i}\rVert ^{2}}{2\sigma ^{2}}}\right)}}</annotation>

</semantics>

</math><img src="./6b2ce5e8e820db4d2334de74d76097e7c9b4f148.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; margin-left: -0.089ex; width:40.27ex; height:7.509ex;" alt="{\displaystyle p(s|i)={\frac {1}{(2\pi \sigma ^{2})^{D/2}}}\exp {\left(-{\frac {\lVert s-m_{i}\rVert ^{2}}{2\sigma ^{2}}}\right)}}" loading="lazy"></dd></dl>

The membership probabilities <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(i)={\frac {1}{M}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(i)={\frac {1}{M}}}</annotation>

</semantics>

</math><img src="./fc475aae2f223267347f5172bd18357ab1fa6ad6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.734ex; height:5.176ex;" alt="{\displaystyle P(i)={\frac {1}{M}}}" loading="lazy"> is equal for all GMM components. The weight of the uniform distribution is denoted as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in [0,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\in [0,1]}</annotation>

</semantics>

</math><img src="./0acf63ae6e8341671a616ff0b763b44d94bd6669.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.157ex; height:2.843ex;" alt="{\displaystyle w\in [0,1]}" loading="lazy">. The mixture model is then:

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(s)=w{\frac {1}{N}}+(1-w)\sum _{i=1}^{M}{\frac {1}{M}}p(s|i)}</annotation>

</semantics>

</math><img src="./07360514320e398ad02e2e370d54170dbadf8160.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; margin-left: -0.089ex; width:35.064ex; height:7.343ex;" alt="{\displaystyle p(s)=w{\frac {1}{N}}+(1-w)\sum _{i=1}^{M}{\frac {1}{M}}p(s|i)}" loading="lazy"></td> <td></td> <td class="nowrap">cpd.2</td></tr></tbody></table>

The GMM centroids are re-parametrized by a set of parameters <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> estimated by maximizing the likelihood. This is equivalent to minimizing the negative <a href="Likelihood_function#Log-likelihood" title="Likelihood function">log-likelihood function</a>:

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(\theta ,\sigma ^{2})=-\sum _{j=1}^{N}\log \sum _{i=1}^{M+1}P(i)p(s|i)}</annotation>

</semantics>

</math><img src="./fdab642e6cc2b442b3ce97f3158833ba3c9eea20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:34.579ex; height:7.676ex;" alt="{\displaystyle E(\theta ,\sigma ^{2})=-\sum _{j=1}^{N}\log \sum _{i=1}^{M+1}P(i)p(s|i)}" loading="lazy"></td> <td></td> <td class="nowrap">cpd.3</td></tr></tbody></table>

where it is assumed that the data is <a href="Independent_and_identically_distributed" class="mw-redirect" title="Independent and identically distributed">independent and identically distributed</a>. The correspondence probability between two points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>

</semantics>

</math><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{j}}</annotation>

</semantics>

</math><img src="./c6a350c64508aef872d4e72ee677746ef7a20f72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2ex; height:2.343ex;" alt="{\displaystyle s_{j}}" loading="lazy"> is defined as the <a href="Posterior_probability" title="Posterior probability">posterior probability</a> of the GMM centroid given the data point:

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(i|s_{j})={\frac {P(i)p(s_{j}|i)}{p(s_{j})}}}</annotation>

</semantics>

</math><img src="./a95568cfab85593c575c27913ed20cdec30c52f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:21.724ex; height:6.509ex;" alt="{\displaystyle P(i|s_{j})={\frac {P(i)p(s_{j}|i)}{p(s_{j})}}}" loading="lazy"></dd></dl>

The <a href="Expectation_maximization" class="mw-redirect" title="Expectation maximization">expectation maximization</a> (EM) algorithm is used to find <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma ^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}}</annotation>

</semantics>

</math><img src="./53a5c55e536acf250c1d3e0f754be5692b843ef5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.385ex; height:2.676ex;" alt="{\displaystyle \sigma ^{2}}" loading="lazy">. The EM algorithm consists of two steps. First, in the E-step or estimation step, it guesses the values of parameters ("old" parameter values) and then uses <a href="Bayes'_theorem" title="Bayes' theorem">Bayes' theorem</a> to compute the posterior probability distributions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P^{\text{old}}(i,s_{j})}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P^{\text{old}}(i,s_{j})}</annotation>

</semantics>

</math><img src="./d9176319eee884e68081d0b79d24a75d52f234c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.893ex; height:3.343ex;" alt="{\displaystyle P^{\text{old}}(i,s_{j})}" loading="lazy"> of mixture components. Second, in the M-step or maximization step, the "new" parameter values are then found by minimizing the expectation of the complete negative log-likelihood function, i.e. the cost function:

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {cost} =-\sum _{j=1}^{N}\sum _{i=1}^{M+1}P^{\text{old}}(i|s_{j})\log(P^{\text{new}}(i)p^{\text{new}}(s_{j}|i))}</annotation>

</semantics>

</math><img src="./03d66823f9cbc69659604d28508813486a8fc5a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:48.927ex; height:7.676ex;" alt="{\displaystyle \operatorname {cost} =-\sum _{j=1}^{N}\sum _{i=1}^{M+1}P^{\text{old}}(i|s_{j})\log(P^{\text{new}}(i)p^{\text{new}}(s_{j}|i))}" loading="lazy"></td> <td></td> <td class="nowrap">cpd.4</td></tr></tbody></table>

Ignoring constants independent of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma }</annotation>

</semantics>

</math><img src="./59f59b7c3e6fdb1d0365a494b81fb9a696138c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle \sigma }" loading="lazy">, Equation (<a href="#math_cpd.4">cpd.4</a>) can be expressed thus:

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {cost} (\theta ,\sigma ^{2})={\frac {1}{2\sigma ^{2}}}\sum _{j=1}^{N}\sum _{i=1}^{M+1}P^{\text{old}}(i|s_{j})\lVert s_{j}-T(m_{i},\theta )\rVert ^{2}+{\frac {N_{\mathbf {P} }D}{2}}\log {\sigma ^{2}}}</annotation>

</semantics>

</math><img src="./452265bc25e8e423b0456042ba78d9d10f59fd54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:67.417ex; height:7.676ex;" alt="{\displaystyle \operatorname {cost} (\theta ,\sigma ^{2})={\frac {1}{2\sigma ^{2}}}\sum _{j=1}^{N}\sum _{i=1}^{M+1}P^{\text{old}}(i|s_{j})\lVert s_{j}-T(m_{i},\theta )\rVert ^{2}+{\frac {N_{\mathbf {P} }D}{2}}\log {\sigma ^{2}}}" loading="lazy"></td> <td></td> <td class="nowrap">cpd.5</td></tr></tbody></table>

where

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{\mathbf {P} }=\sum _{j=0}^{N}\sum _{i=0}^{M}P^{\text{old}}(i|s_{j})\leq N}</annotation>

</semantics>

</math><img src="./25d9332d5dfe0fab510bf2be9e29a76d023c495f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:28.641ex; height:7.676ex;" alt="{\displaystyle N_{\mathbf {P} }=\sum _{j=0}^{N}\sum _{i=0}^{M}P^{\text{old}}(i|s_{j})\leq N}" loading="lazy"></dd></dl>

with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=N_{\mathbf {P} }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=N_{\mathbf {P} }}</annotation>

</semantics>

</math><img src="./fe5943053ca52292539d1d3d674ecc987e929db0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.552ex; height:2.509ex;" alt="{\displaystyle N=N_{\mathbf {P} }}" loading="lazy"> only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=0}</annotation>

</semantics>

</math><img src="./9bb71c9fa0018f0752a2384a7ab9f1c2b628771e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.925ex; height:2.176ex;" alt="{\displaystyle w=0}" loading="lazy">. The posterior probabilities of GMM components computed using previous parameter values <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P^{\text{old}}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P^{\text{old}}}</annotation>

</semantics>

</math><img src="./392f796cce0ff0cee5f1fce5df1e1f16fa4ae93b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.247ex; height:2.676ex;" alt="{\displaystyle P^{\text{old}}}" loading="lazy"> is:

<msup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P^{\text{old}}(i|s_{j})={\frac {\exp \left(-{\frac {1}{2\sigma ^{{\text{old}}2}}}\lVert s_{j}-T(m_{i},\theta ^{\text{old}})\rVert ^{2}\right)}{\sum _{k=1}^{M}\exp \left(-{\frac {1}{2\sigma ^{{\text{old}}2}}}\lVert s_{j}-T(m_{k},\theta ^{\text{old}})\rVert ^{2}\right)+(2\pi \sigma ^{2})^{\frac {D}{2}}{\frac {w}{1-w}}{\frac {M}{N}}}}}</annotation>

</semantics>

</math><img src="./9f1b0bf6b4a138b2e4b44af7c9e9de1b5d9bc8fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.838ex; width:70.541ex; height:10.509ex;" alt="{\displaystyle P^{\text{old}}(i|s_{j})={\frac {\exp \left(-{\frac {1}{2\sigma ^{{\text{old}}2}}}\lVert s_{j}-T(m_{i},\theta ^{\text{old}})\rVert ^{2}\right)}{\sum _{k=1}^{M}\exp \left(-{\frac {1}{2\sigma ^{{\text{old}}2}}}\lVert s_{j}-T(m_{k},\theta ^{\text{old}})\rVert ^{2}\right)+(2\pi \sigma ^{2})^{\frac {D}{2}}{\frac {w}{1-w}}{\frac {M}{N}}}}}" loading="lazy"></td> <td></td> <td class="nowrap">cpd.6</td></tr></tbody></table>

Minimizing the cost function in Equation (<a href="#math_cpd.5">cpd.5</a>) necessarily decreases the negative log-likelihood function E in Equation (<a href="#math_cpd.3">cpd.3</a>) unless it is already at a local minimum.<a href="#cite_note-cpdmyronenko2-13">[13]</a> Thus, the algorithm can be expressed using the following pseudocode, where the point sets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {M}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {M}}}</annotation>

</semantics>

</math><img src="./2cc2abebd45ec020509a0ec548b67c9a2cb7cecd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.791ex; height:2.176ex;" alt="{\displaystyle {\mathcal {M}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy"> are represented as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M\times D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\times D}</annotation>

</semantics>

</math><img src="./17febfc98577f7237628332e925fb6cba01c440f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.207ex; height:2.176ex;" alt="{\displaystyle M\times D}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\times D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\times D}</annotation>

</semantics>

</math><img src="./4254cdd7c93ba43f49d572991155a07e0f2012ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.828ex; height:2.176ex;" alt="{\displaystyle N\times D}" loading="lazy"> matrices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {M} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {M} }</annotation>

</semantics>

</math><img src="./e499ae5946af9c09777ada933051b3669d3372c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.537ex; height:2.176ex;" alt="{\displaystyle \mathbf {M} }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {S} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {S} }</annotation>

</semantics>

</math><img src="./ac8a515de34f0af7d15de46f73bf674950d444a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.485ex; height:2.176ex;" alt="{\displaystyle \mathbf {S} }" loading="lazy"> respectively:<a href="#cite_note-cpdmyronenko2-13">[13]</a>

<pre>algorithm CPD<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ({\mathcal {M}},{\mathcal {S}})}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ({\mathcal {M}},{\mathcal {S}})}</annotation>

</semantics>

</math><img src="./a3274d9795d894cf4f995a61b88ee34e40a6dc7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.126ex; height:2.843ex;" alt="{\displaystyle ({\mathcal {M}},{\mathcal {S}})}" loading="lazy">

θ := θ0

initialize 0 ≤ w ≤ 1

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}:={\frac {1}{DNM}}\sum _{j=1}^{N}\sum _{i=1}^{M}\lVert s_{j}-m_{i}\rVert ^{2}}</annotation>

</semantics>

</math><img src="./96e2fc9c05e5a00a84bf821c01b134b590db06ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:31.94ex; height:7.676ex;" alt="{\displaystyle \sigma ^{2}:={\frac {1}{DNM}}\sum _{j=1}^{N}\sum _{i=1}^{M}\lVert s_{j}-m_{i}\rVert ^{2}}" loading="lazy">

while not registered:

// E-step, compute P

for i ∊ [1, M] and j ∊ [1, N]:

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{ij}:={\frac {\exp \left(-{\frac {1}{2\sigma ^{2}}}\lVert s_{j}-T(m_{i},\theta )\rVert ^{2}\right)}{\sum _{k=1}^{M}\exp \left(-{\frac {1}{2\sigma ^{2}}}\lVert s_{j}-T(m_{k},\theta )\rVert ^{2}\right)+(2\pi \sigma ^{2})^{\frac {D}{2}}{\frac {w}{1-w}}{\frac {M}{N}}}}}</annotation>

</semantics>

</math><img src="./bd6ef3588492d6719c01643962f1d70b907c8f67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.838ex; margin-left: -0.089ex; width:60.211ex; height:10.509ex;" alt="{\displaystyle p_{ij}:={\frac {\exp \left(-{\frac {1}{2\sigma ^{2}}}\lVert s_{j}-T(m_{i},\theta )\rVert ^{2}\right)}{\sum _{k=1}^{M}\exp \left(-{\frac {1}{2\sigma ^{2}}}\lVert s_{j}-T(m_{k},\theta )\rVert ^{2}\right)+(2\pi \sigma ^{2})^{\frac {D}{2}}{\frac {w}{1-w}}{\frac {M}{N}}}}}" loading="lazy">

// M-step, solve for optimal transformation

{θ, σ2} := solve(S, M, P)

return θ

</pre>

where the vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {1} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {1} }</annotation>

</semantics>

</math><img src="./235ffc0f1788b720aef5caa7b97246a84421fd0e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.337ex; height:2.176ex;" alt="{\displaystyle \mathbf {1} }" loading="lazy"> is a column vector of ones. The <code>solve</code> function differs by the type of registration performed. For example, in rigid registration, the output is a scale a, a rotation matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {R} }</annotation>

</semantics>

</math><img src="./5de85fcc2a00d8ba14aae84aeef812d7fef4b3d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.003ex; height:2.176ex;" alt="{\displaystyle \mathbf {R} }" loading="lazy">, and a translation vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {t} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {t} }</annotation>

</semantics>

</math><img src="./16ff63cc74a931900e79b3caacbae3fa8cc66845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.039ex; height:2.009ex;" alt="{\displaystyle \mathbf {t} }" loading="lazy">. The parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> can be written as a tuple of these:

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta =\lbrace a,\mathbf {R} ,\mathbf {t} \rbrace }</annotation>

</semantics>

</math><img src="./46c71f11dd5343e398752a0e8dd2502285857913.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.854ex; height:2.843ex;" alt="{\displaystyle \theta =\lbrace a,\mathbf {R} ,\mathbf {t} \rbrace }" loading="lazy"></dd></dl>

which is initialized to one, the <a href="Identity_matrix" title="Identity matrix">identity matrix</a>, and a column vector of zeroes:

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta _{0}=\lbrace 1,\mathbf {I} ,\mathbf {0} \rbrace }</annotation>

</semantics>

</math><img src="./7a00d6f55c1a5dfebb6ca88f96115d130d6a6491.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.149ex; height:2.843ex;" alt="{\displaystyle \theta _{0}=\lbrace 1,\mathbf {I} ,\mathbf {0} \rbrace }" loading="lazy"></dd></dl>

The aligned point set is:

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(\mathbf {M} )=a\mathbf {M} \mathbf {R} ^{T}+\mathbf {1} \mathbf {t} ^{T}}</annotation>

</semantics>

</math><img src="./639b0b7c99b92f8316046c199764e53146fb508f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.847ex; height:3.176ex;" alt="{\displaystyle T(\mathbf {M} )=a\mathbf {M} \mathbf {R} ^{T}+\mathbf {1} \mathbf {t} ^{T}}" loading="lazy"></dd></dl>

The <code>solve_rigid</code> function for rigid registration can then be written as follows, with derivation of the algebra explained in Myronenko's 2010 paper.<a href="#cite_note-cpdmyronenko2-13">[13]</a>

<pre>solve_rigid(S, M, P)

NP := 1TP1

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{s}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {S} ^{T}\mathbf {P} ^{T}\mathbf {1} }</annotation>

</semantics>

</math><img src="./9fb22673314c9b21fc61e6506a9750be4b87f4ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:17.804ex; height:5.509ex;" alt="{\displaystyle \mu _{s}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {S} ^{T}\mathbf {P} ^{T}\mathbf {1} }" loading="lazy">

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{m}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {M} ^{T}\mathbf {P} \mathbf {1} }</annotation>

</semantics>

</math><img src="./aa11630c33a4568e009c3bd31a7ae965420b6ff7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:18.138ex; height:5.509ex;" alt="{\displaystyle \mu _{m}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {M} ^{T}\mathbf {P} \mathbf {1} }" loading="lazy">

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}}</annotation>

</semantics>

</math><img src="./311885d1e85f1411a672d0f860ca897e0df6e6b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.684ex; height:3.343ex;" alt="{\displaystyle {\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}}" loading="lazy">

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}}</annotation>

</semantics>

</math><img src="./f5b443c1a8930fee95af023e78c85ee2d0428a82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.074ex; height:3.343ex;" alt="{\displaystyle {\hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}}" loading="lazy">

</mrow>

<mover>

<msup>

</mrow>

</mrow>

</msup>

</mover>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

<mover>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {A} :={\hat {\mathbf {S} ^{T}}}\mathbf {P} ^{T}{\hat {\mathbf {M} }}}</annotation>

</semantics>

</math><img src="./66c18dc039045826a865c7bad0ebf55ed0605fa4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.393ex; height:3.343ex;" alt="{\displaystyle \mathbf {A} :={\hat {\mathbf {S} ^{T}}}\mathbf {P} ^{T}{\hat {\mathbf {M} }}}" loading="lazy">

U, V := svd(A) // the <a href="Singular_value_decomposition" title="Singular value decomposition">singular value decomposition</a> of A = UΣVT

C := diag(1, …, 1, det(UVT)) // diag(ξ)is the <a href="Diagonal_matrix" title="Diagonal matrix">diagonal matrix</a> formed from vector ξ

R := UCVT

<mfrac>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

<mrow>

<msup>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a:={\frac {\operatorname {tr} (\mathbf {A} ^{T}\mathbf {R} )}{\operatorname {tr} (\mathbf {{\hat {\mathbf {M} }}^{T}\operatorname {diag} (\mathbf {P} \mathbf {1} ){\hat {\mathbf {M} }}} )}}}</annotation>

</semantics>

</math><img src="./d5e652a0d8e5774abdce36a8b1e3bc456620c63c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:25.952ex; height:7.843ex;" alt="{\displaystyle a:={\frac {\operatorname {tr} (\mathbf {A} ^{T}\mathbf {R} )}{\operatorname {tr} (\mathbf {{\hat {\mathbf {M} }}^{T}\operatorname {diag} (\mathbf {P} \mathbf {1} ){\hat {\mathbf {M} }}} )}}}" loading="lazy"> // tr is the <a href="Trace_(linear_algebra)" title="Trace (linear algebra)">trace</a> of a matrix

t := μs − aRμm

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msup>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<mover>

</mrow>

</mover>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}:={\frac {1}{N_{\mathbf {P} }D}}(\operatorname {tr} (\mathbf {{\hat {\mathbf {S} }}^{T}\operatorname {diag} (\mathbf {P} ^{T}\mathbf {1} ){\hat {\mathbf {S} }}} )-a\operatorname {tr} (\mathbf {A} ^{T}\mathbf {R} ))}</annotation>

</semantics>

</math><img src="./aa73a42b216a89a0a6a54e4b131a9eb1712d42cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:47.168ex; height:5.509ex;" alt="{\displaystyle \sigma ^{2}:={\frac {1}{N_{\mathbf {P} }D}}(\operatorname {tr} (\mathbf {{\hat {\mathbf {S} }}^{T}\operatorname {diag} (\mathbf {P} ^{T}\mathbf {1} ){\hat {\mathbf {S} }}} )-a\operatorname {tr} (\mathbf {A} ^{T}\mathbf {R} ))}" loading="lazy">

return {a, R, t}, σ2

</pre>

For affine registration, where the goal is to find an <a href="Affine_transformation" title="Affine transformation">affine transformation</a> instead of a rigid one, the output is an affine transformation matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {B} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {B} }</annotation>

</semantics>

</math><img src="./cafb0ef39b0f5ffa23c170aa7f7b4e718327c4d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.901ex; height:2.176ex;" alt="{\displaystyle \mathbf {B} }" loading="lazy"> and a translation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {t} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {t} }</annotation>

</semantics>

</math><img src="./16ff63cc74a931900e79b3caacbae3fa8cc66845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.039ex; height:2.009ex;" alt="{\displaystyle \mathbf {t} }" loading="lazy"> such that the aligned point set is:

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(\mathbf {M} )=\mathbf {M} \mathbf {B} ^{T}+\mathbf {1} \mathbf {t} ^{T}}</annotation>

</semantics>

</math><img src="./565b61968503683c083569f9ec8fea8ad6e976c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.515ex; height:3.176ex;" alt="{\displaystyle T(\mathbf {M} )=\mathbf {M} \mathbf {B} ^{T}+\mathbf {1} \mathbf {t} ^{T}}" loading="lazy"></dd></dl>

The <code>solve_affine</code> function for rigid registration can then be written as follows, with derivation of the algebra explained in Myronenko's 2010 paper.<a href="#cite_note-cpdmyronenko2-13">[13]</a>

<pre>solve_affine(S, M, P)

NP := 1TP1

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{s}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {S} ^{T}\mathbf {P} ^{T}\mathbf {1} }</annotation>

</semantics>

</math><img src="./9fb22673314c9b21fc61e6506a9750be4b87f4ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:17.804ex; height:5.509ex;" alt="{\displaystyle \mu _{s}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {S} ^{T}\mathbf {P} ^{T}\mathbf {1} }" loading="lazy">

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{m}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {M} ^{T}\mathbf {P} \mathbf {1} }</annotation>

</semantics>

</math><img src="./aa11630c33a4568e009c3bd31a7ae965420b6ff7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:18.138ex; height:5.509ex;" alt="{\displaystyle \mu _{m}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {M} ^{T}\mathbf {P} \mathbf {1} }" loading="lazy">

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}}</annotation>

</semantics>

</math><img src="./311885d1e85f1411a672d0f860ca897e0df6e6b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.684ex; height:3.343ex;" alt="{\displaystyle {\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}}" loading="lazy">

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}}</annotation>

</semantics>

</math><img src="./f5b443c1a8930fee95af023e78c85ee2d0428a82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.074ex; height:3.343ex;" alt="{\displaystyle {\hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}}" loading="lazy">

</mrow>

<msup>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

<mover>

</mrow>

</mover>

</mrow>

<msup>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

<mover>

</mrow>

</mover>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {B} :=({\hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat {\mathbf {M} }})({\hat {\mathbf {M} }}^{T}\operatorname {diag} (\mathbf {P} \mathbf {1} ){\hat {\mathbf {M} }})^{-1}}</annotation>

</semantics>

</math><img src="./e33aad4a7fab1a579b47e3ebfad16c0fa5776f03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.314ex; height:3.843ex;" alt="{\displaystyle \mathbf {B} :=({\hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat {\mathbf {M} }})({\hat {\mathbf {M} }}^{T}\operatorname {diag} (\mathbf {P} \mathbf {1} ){\hat {\mathbf {M} }})^{-1}}" loading="lazy">

t := μs − Bμm

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msup>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<mover>

</mrow>

</mover>

</mrow>

<msup>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

<mover>

</mrow>

</mover>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}:={\frac {1}{N_{\mathbf {P} }D}}(\operatorname {tr} ({\hat {\mathbf {S} }}^{T}\operatorname {diag} (\mathbf {P} ^{T}\mathbf {1} ){\hat {\mathbf {S} }})-\operatorname {tr} ({\hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat {\mathbf {M} }}\mathbf {B} ^{T}))}</annotation>

</semantics>

</math><img src="./7f37a3b103534f1c431e0d8f4f86a8f5d9350561.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:51.473ex; height:5.509ex;" alt="{\displaystyle \sigma ^{2}:={\frac {1}{N_{\mathbf {P} }D}}(\operatorname {tr} ({\hat {\mathbf {S} }}^{T}\operatorname {diag} (\mathbf {P} ^{T}\mathbf {1} ){\hat {\mathbf {S} }})-\operatorname {tr} ({\hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat {\mathbf {M} }}\mathbf {B} ^{T}))}" loading="lazy">

return {B, t}, σ2

</pre>

It is also possible to use CPD with non-rigid registration using a parametrization derived using <a href="Calculus_of_variations" title="Calculus of variations">calculus of variations</a>.<a href="#cite_note-cpdmyronenko2-13">[13]</a>

Sums of Gaussian distributions can be computed in <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a> using the fast Gauss transform (FGT).<a href="#cite_note-cpdmyronenko2-13">[13]</a> Consequently, the <a href="Time_complexity" title="Time complexity">time complexity</a> of CPD is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(M+N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(M+N)}</annotation>

</semantics>

</math><img src="./92accdfb7b2bf51f95b0f336a0e8e2b7b266d25f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.929ex; height:2.843ex;" alt="{\displaystyle O(M+N)}" loading="lazy">, which is asymptotically much faster than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(MN)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(MN)}</annotation>

</semantics>

</math><img src="./ee63b96e5439a02e97fd879b623275fbda6be74a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.088ex; height:2.843ex;" alt="{\displaystyle O(MN)}" loading="lazy"> methods.<a href="#cite_note-cpdmyronenko2-13">[13]</a>

<div class="mw-heading mw-heading4"><h4 id="Bayesian_coherent_point_drift_(BCPD)">Bayesian coherent point drift (BCPD)</h4></div>

A variant of coherent point drift, called Bayesian coherent point drift (BCPD), was derived through a Bayesian formulation of point set registration.

BCPD has several advantages over CPD, e.g., (1) nonrigid and rigid registrations can be performed in a single algorithm, (2) the algorithm can be accelerated regardless of the Gaussianity of a Gram matrix to define motion coherence, (3) the algorithm is more robust against outliers because of a more reasonable definition of an outlier distribution. Additionally, in the Bayesian formulation, motion coherence was introduced through a prior distribution of displacement vectors, providing a clear difference between tuning parameters that control motion coherence. BCPD was further accelerated by a method called BCPD++, which is a three-step procedure composed of (1) downsampling of point sets, (2) registration of downsampled point sets, and (3) interpolation of a deformation field.

The method can register point sets composed of more than 10M points while maintaining its registration accuracy.

<div class="mw-heading mw-heading4"><h4 id="Coherent_point_drift_with_local_surface_geometry_(LSG-CPD)">Coherent point drift with local surface geometry (LSG-CPD)</h4></div>

An variant of coherent point drift called CPD with Local Surface Geometry (LSG-CPD) for rigid point cloud registration.<a href="#cite_note-44">[44]</a> The method adaptively adds different levels of point-to-plane penalization on top of the point-to-point penalization based on the flatness of the local surface. This results in GMM components with anisotropic covariances, instead of the isotropic covariances in the original CPD.<a href="#cite_note-cpdmyronenko2-13">[13]</a> The anisotropic covariance matrix is modeled as:

</mrow>

</mrow>

</msubsup>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma _{m}^{-1}={\frac {1}{\sigma ^{2}}}\left(\alpha _{m}\mathbf {n} _{m}\mathbf {n} _{m}^{T}+\mathbf {I} \right)}</annotation>

</semantics>

</math><img src="./cda9be75d48c09256c89183394394dbce9524947.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:26.185ex; height:5.509ex;" alt="{\displaystyle \Sigma _{m}^{-1}={\frac {1}{\sigma ^{2}}}\left(\alpha _{m}\mathbf {n} _{m}\mathbf {n} _{m}^{T}+\mathbf {I} \right)}" loading="lazy"></td> <td></td> <td class="nowrap">lsg-cpd.1</td></tr></tbody></table>

where

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<mrow>

<mrow>

<mrow>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

</mrow>

<mrow>

<mrow>

<mrow>

<mrow>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{m}={\frac {1-\exp \left(\lambda \left(3-{\frac {1}{\kappa _{m}}}\right)\right)}{1+\exp \left(\lambda \left(3-{\frac {1}{\kappa _{m}}}\right)\right)}}\alpha _{max}}</annotation>

</semantics>

</math><img src="./8c74723009e8a3348556113040e94d110cb3fb7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.505ex; width:34.04ex; height:10.176ex;" alt="{\displaystyle \alpha _{m}={\frac {1-\exp \left(\lambda \left(3-{\frac {1}{\kappa _{m}}}\right)\right)}{1+\exp \left(\lambda \left(3-{\frac {1}{\kappa _{m}}}\right)\right)}}\alpha _{max}}" loading="lazy"></td> <td></td> <td class="nowrap">lsg-cpd.2</td></tr></tbody></table>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma _{m}}</annotation>

</semantics>

</math><img src="./62b78e616f0f01d6deef72e313f64e515af7f303.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.353ex; height:2.509ex;" alt="{\displaystyle \Sigma _{m}}" loading="lazy"> is the anisotropic covariance matrix of the m-th point in the target set; <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {n} _{m}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {n} _{m}}</annotation>

</semantics>

</math><img src="./ad849bf1a649439a1d7f10e74410ad9308925c5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.16ex; height:2.009ex;" alt="{\displaystyle \mathbf {n} _{m}}" loading="lazy"> is the normal vector corresponding to the same point; <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {I} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {I} }</annotation>

</semantics>

</math><img src="./8a458c8aeb096ce732abf346ae8edf3e4f53a126.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.014ex; height:2.176ex;" alt="{\displaystyle \mathbf {I} }" loading="lazy"> is an identity matrix, serving as a regularizer, pulling the problem away from ill-posedness. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{m}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{m}}</annotation>

</semantics>

</math><img src="./251a293d0e46862cdeba1f4a095eb3c6415fa69b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.163ex; height:2.009ex;" alt="{\displaystyle \alpha _{m}}" loading="lazy"> is penalization coefficient (a modified sigmoid function), which is set adaptively to add different levels of point-to-plane penalization depending on how flat the local surface is. This is realized by evaluating the surface variation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \kappa _{m}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \kappa _{m}}</annotation>

</semantics>

</math><img src="./3cf3fff473bfb0cf76cae46f5bcf2d4dd55f789b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.014ex; height:2.009ex;" alt="{\displaystyle \kappa _{m}}" loading="lazy"><a href="#cite_note-45">[45]</a> within the neighborhood of the m-th target point. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{max}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{max}}</annotation>

</semantics>

</math><img src="./45260dc81cdf5b45fe47876dedccd40a3eb03978.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.972ex; height:2.009ex;" alt="{\displaystyle \alpha _{max}}" loading="lazy"> is the upper bound of the penalization.

The point cloud registration is formulated as a maximum likelihood estimation (MLE) problem and solve it with the Expectation-Maximization (EM) algorithm. In the E step, the correspondence computation is recast into simple matrix manipulations and efficiently computed on a GPU. In the M step, an unconstrained optimization on a matrix Lie group is designed to efficiently update the rigid transformation of the registration. Taking advantage of the local geometric covariances, the method shows a superior performance in accuracy and robustness to noise and outliers, compared with the baseline CPD.<a href="#cite_note-46">[46]</a> An enhanced runtime performance is expected thanks to the GPU accelerated correspondence calculation. An implementation of the LSG-CPD is <a rel="nofollow" class="external text" href="https://github.com/ChirikjianLab/LSG-CPD">open-sourced here</a>.

<div class="mw-heading mw-heading3"><h3 id="Sorting_the_Correspondence_Space_(SCS)">Sorting the Correspondence Space (SCS)</h3></div>

This algorithm was introduced in 2013 by H. Assalih to accommodate sonar image registration.<a href="#cite_note-47">[47]</a> These types of images tend to have high amounts of noise, so it is expected to have many outliers in the point sets to match. SCS delivers high robustness against outliers and can surpass ICP and CPD performance in the presence of outliers. SCS doesn't use iterative optimization in high dimensional space and is neither probabilistic nor spectral. SCS can match rigid and non-rigid transformations, and performs best when the target transformation is between three and six <a href="Degrees_of_freedom" title="Degrees of freedom">degrees of freedom</a>.

<ul><li><a href="Point_feature_matching" class="mw-redirect" title="Point feature matching">Point feature matching</a></li>

<li><a href="Point-set_triangulation" title="Point-set triangulation">Point-set triangulation</a></li>

<li><a href="Normal_distributions_transform" title="Normal distributions transform">Normal distributions transform</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFZhangSingh2015" class="citation book cs1">Zhang, Ji; Singh, Sanjiv (May 2015). "Visual-lidar odometry and mapping: Low-drift, robust, and fast". 2015 IEEE International Conference on Robotics and Automation (ICRA). pp. 2174–2181. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FICRA.2015.7139486">10.1109/ICRA.2015.7139486</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4799-6923-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6054487">6054487</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFChoiZhouKoltun2015" class="citation journal cs1">Choi, Sungjoon; Zhou, Qian-Yi; Koltun, Vladlen (2015). <a rel="nofollow" class="external text" href="https://www.cv-foundation.org/openaccess/content_cvpr_2015/papers/Choi_Robust_Reconstruction_of_2015_CVPR_paper.pdf">"Robust reconstruction of indoor scenes"</a> (PDF). Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR): 5556–5565.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFLaiBoRenFox2011" class="citation book cs1">Lai, Kevin; Bo, Liefeng; Ren, Xiaofeng; Fox, Dieter (May 2011). "A large-scale hierarchical multi-view RGB-D object dataset". 2011 IEEE International Conference on Robotics and Automation. pp. 1817–1824. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.190.1598">10.1.1.190.1598</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FICRA.2011.5980382">10.1109/ICRA.2011.5980382</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-61284-386-5</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14986048">14986048</a>.</cite>

</li>

<li id="cite_note-:4-4">^ <a href="#cite_ref-:4_4-0">a</a> <a href="#cite_ref-:4_4-1">b</a> <a href="#cite_ref-:4_4-2">c</a> <cite id="CITEREFYangCarlone2019" class="citation journal cs1">Yang, Heng; Carlone, Luca (2019). "A polynomial-time solution for robust registration with extreme outlier rates". Robotics: Science and Systems. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1903.08588">1903.08588</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.15607%2FRSS.2019.XV.003">10.15607/RSS.2019.XV.003</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-9923747-5-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:84186750">84186750</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFCalliSinghBruceWalsman2017" class="citation journal cs1">Calli, Berk; Singh, Arjun; Bruce, James; Walsman, Aaron; Konolige, Kurt; Srinivasa, Siddhartha; Abbeel, Pieter; Dollar, Aaron M (2017-03-01). "Yale-CMU-Berkeley dataset for robotic manipulation research". The International Journal of Robotics Research. 36 (3): 261–268. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1177%2F0278364917700714">10.1177/0278364917700714</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0278-3649">0278-3649</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6522002">6522002</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFCadenaCarloneCarrilloLatif2016" class="citation journal cs1">Cadena, Cesar; Carlone, Luca; Carrillo, Henry; Latif, Yasir; Scaramuzza, Davide; Neira, José; Reid, Ian; Leonard, John J. (December 2016). "Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age". IEEE Transactions on Robotics. 32 (6): 1309–1332. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1606.05830">1606.05830</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2016arXiv160605830C">2016arXiv160605830C</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTRO.2016.2624754">10.1109/TRO.2016.2624754</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1941-0468">1941-0468</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2596787">2596787</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFMur-ArtalMontielTardós2015" class="citation journal cs1">Mur-Artal, Raúl; Montiel, J. M. M.; Tardós, Juan D. (October 2015). "ORB-SLAM: A Versatile and Accurate Monocular SLAM System". IEEE Transactions on Robotics. 31 (5): 1147–1163. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1502.00956">1502.00956</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2015arXiv150200956M">2015arXiv150200956M</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTRO.2015.2463671">10.1109/TRO.2015.2463671</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1941-0468">1941-0468</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:206775100">206775100</a>.</cite>

</li>

<li id="cite_note-:6-8">^ <a href="#cite_ref-:6_8-0">a</a> <a href="#cite_ref-:6_8-1">b</a> <a href="#cite_ref-:6_8-2">c</a> <cite id="CITEREFYangCarlone2019" class="citation journal cs1">Yang, Heng; Carlone, Luca (2019). <a rel="nofollow" class="external text" href="http://openaccess.thecvf.com/content_ICCV_2019/papers/Yang_A_Quaternion-Based_Certifiably_Optimal_Solution_to_the_Wahba_Problem_With_ICCV_2019_paper.pdf">"A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers"</a> (PDF). Proceedings of the IEEE International Conference on Computer Vision (ICCV): 1665–1674. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1905.12536">1905.12536</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2019arXiv190512536Y">2019arXiv190512536Y</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFNewcombeIzadiHilligesMolyneaux2011" class="citation book cs1">Newcombe, Richard A.; Izadi, Shahram; Hilliges, Otmar; Molyneaux, David; Kim, David; Davison, Andrew J.; Kohi, Pushmeet; Shotton, Jamie; Hodges, Steve; Fitzgibbon, Andrew (October 2011). "KinectFusion: Real-time dense surface mapping and tracking". 2011 10th IEEE International Symposium on Mixed and Augmented Reality. pp. 127–136. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.453.53">10.1.1.453.53</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FISMAR.2011.6092378">10.1109/ISMAR.2011.6092378</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4577-2183-0</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11830123">11830123</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFAudetteFerriePeters2000" class="citation journal cs1">Audette, Michel A.; Ferrie, Frank P.; Peters, Terry M. (2000-09-01). "An algorithmic overview of surface registration techniques for medical imaging". Medical Image Analysis. 4 (3): 201–217. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS1361-8415%2800%2900014-1">10.1016/S1361-8415(00)00014-1</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1361-8415">1361-8415</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/11145309">11145309</a>.</cite>

</li>

<li id="cite_note-gmmjian-11">^ <a href="#cite_ref-gmmjian_11-0">a</a> <a href="#cite_ref-gmmjian_11-1">b</a> <cite id="CITEREFJianVemuri2011" class="citation journal cs1">Jian, Bing; Vemuri, Baba C. (2011). "Robust Point Set Registration Using Gaussian Mixture Models". IEEE Transactions on Pattern Analysis and Machine Intelligence. 33 (8): 1633–1645. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftpami.2010.223">10.1109/tpami.2010.223</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/21173443">21173443</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10923565">10923565</a>.</cite>

</li>

<li id="cite_note-lmfitzgibbon-12">^ <a href="#cite_ref-lmfitzgibbon_12-0">a</a> <a href="#cite_ref-lmfitzgibbon_12-1">b</a> <cite id="CITEREFFitzgibbon2003" class="citation journal cs1">Fitzgibbon, Andrew W. (2003). "Robust registration of 2D and 3D point sets". Image and Vision Computing. 21 (13): 1145–1153. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.335.116">10.1.1.335.116</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.imavis.2003.09.004">10.1016/j.imavis.2003.09.004</a>.</cite>

</li>

<li id="cite_note-cpdmyronenko2-13">^ <a href="#cite_ref-cpdmyronenko2_13-0">a</a> <a href="#cite_ref-cpdmyronenko2_13-1">b</a> <a href="#cite_ref-cpdmyronenko2_13-2">c</a> <a href="#cite_ref-cpdmyronenko2_13-3">d</a> <a href="#cite_ref-cpdmyronenko2_13-4">e</a> <a href="#cite_ref-cpdmyronenko2_13-5">f</a> <a href="#cite_ref-cpdmyronenko2_13-6">g</a> <a href="#cite_ref-cpdmyronenko2_13-7">h</a> <a href="#cite_ref-cpdmyronenko2_13-8">i</a> <a href="#cite_ref-cpdmyronenko2_13-9">j</a> <a href="#cite_ref-cpdmyronenko2_13-10">k</a> <a href="#cite_ref-cpdmyronenko2_13-11">l</a> <a href="#cite_ref-cpdmyronenko2_13-12">m</a> <cite id="CITEREFMyronenkoSong2010" class="citation journal cs1">Myronenko, Andriy; Song, Xubo (2010). "Point set registration: Coherent Point drift". IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (2): 2262–2275. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0905.2635">0905.2635</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftpami.2010.46">10.1109/tpami.2010.46</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/20975122">20975122</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10809031">10809031</a>.</cite>

</li>

<li id="cite_note-tpsrpmchui-14">^ <a href="#cite_ref-tpsrpmchui_14-0">a</a> <a href="#cite_ref-tpsrpmchui_14-1">b</a> <a href="#cite_ref-tpsrpmchui_14-2">c</a> <cite id="CITEREFChuiRangarajan2003" class="citation journal cs1">Chui, Haili; Rangarajan, Anand (2003). "A new point matching algorithm for non-rigid registration". Computer Vision and Image Understanding. 89 (2): 114–141. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.4365">10.1.1.7.4365</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS1077-3142%2803%2900009-2">10.1016/S1077-3142(03)00009-2</a>.</cite>

</li>

<li id="cite_note-PCL-Tutorial-15"><a href="#cite_ref-PCL-Tutorial_15-0">^</a> <cite id="CITEREFHolzIchimTombariRusu2015" class="citation journal cs1">Holz, Dirk; Ichim, Alexandru E.; Tombari, Federico; Rusu, Radu B.; Behnke, Sven (2015). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/283198426">"Registration with the Point Cloud Library: A Modular Framework for Aligning in 3-D"</a>. IEEE Robotics & Automation Magazine. 22 (4): 110–124. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FMRA.2015.2432331">10.1109/MRA.2015.2432331</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2621807">2621807</a>.</cite>

</li>

<li id="cite_note-:11-16">^ <a href="#cite_ref-:11_16-0">a</a> <a href="#cite_ref-:11_16-1">b</a> <a href="#cite_ref-:11_16-2">c</a> <cite id="CITEREFHorn1987" class="citation journal cs1">Horn, Berthold K. P. (1987-04-01). "Closed-form solution of absolute orientation using unit quaternions". JOSA A. 4 (4): 629–642. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1987JOSAA...4..629H">1987JOSAA...4..629H</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1364%2FJOSAA.4.000629">10.1364/JOSAA.4.000629</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1520-8532">1520-8532</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11038004">11038004</a>.</cite>

</li>

<li id="cite_note-:12-17">^ <a href="#cite_ref-:12_17-0">a</a> <a href="#cite_ref-:12_17-1">b</a> <cite id="CITEREFArunHuangBlostein1987" class="citation journal cs1 cs1-prop-long-vol">Arun, K. S.; Huang, T. S.; Blostein, S. D. (September 1987). "Least-Squares Fitting of Two 3-D Point Sets". IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-9 (5): 698–700. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTPAMI.1987.4767965">10.1109/TPAMI.1987.4767965</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1939-3539">1939-3539</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/21869429">21869429</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8724100">8724100</a>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFBrialesGonzalez-Jimenez2017" class="citation book cs1">Briales, Jesus; Gonzalez-Jimenez, Javier (July 2017). "Convex Global 3D Registration with Lagrangian Duality". 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 5612–5621. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FCVPR.2017.595">10.1109/CVPR.2017.595</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10630%2F14599">10630/14599</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-5386-0457-1</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11549421">11549421</a>.</cite>

</li>

<li id="cite_note-:5-19">^ <a href="#cite_ref-:5_19-0">a</a> <a href="#cite_ref-:5_19-1">b</a> <a href="#cite_ref-:5_19-2">c</a> <a href="#cite_ref-:5_19-3">d</a> <a href="#cite_ref-:5_19-4">e</a> <cite id="CITEREFYangShiCarlone2020" class="citation arxiv cs1">Yang, Heng; Shi, Jingnan; Carlone, Luca (2020-01-21). "TEASER: Fast and Certifiable Point Cloud Registration". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2001.07715">2001.07715</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.RO">cs.RO</a>].</cite>

</li>

<li id="cite_note-:0-20">^ <a href="#cite_ref-:0_20-0">a</a> <a href="#cite_ref-:0_20-1">b</a> <a href="#cite_ref-:0_20-2">c</a> <cite id="CITEREFParra_BustosChin2018" class="citation journal cs1">Parra Bustos, Álvaro; Chin, Tat-Jun (December 2018). "Guaranteed Outlier Removal for Point Cloud Registration with Correspondences". IEEE Transactions on Pattern Analysis and Machine Intelligence. 40 (12): 2868–2882. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1711.10209">1711.10209</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTPAMI.2017.2773482">10.1109/TPAMI.2017.2773482</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1939-3539">1939-3539</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/29990122">29990122</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3331003">3331003</a>.</cite>

</li>

<li id="cite_note-:1-21">^ <a href="#cite_ref-:1_21-0">a</a> <a href="#cite_ref-:1_21-1">b</a> <cite id="CITEREFChinSuter2017" class="citation journal cs1">Chin, Tat-Jun; Suter, David (2017-02-27). "The Maximum Consensus Problem: Recent Algorithmic Advances". Synthesis Lectures on Computer Vision. 7 (2): 1–194. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2200%2Fs00757ed1v01y201702cov011">10.2200/s00757ed1v01y201702cov011</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2153-1056">2153-1056</a>.</cite>

</li>

<li id="cite_note-:2-22">^ <a href="#cite_ref-:2_22-0">a</a> <a href="#cite_ref-:2_22-1">b</a> <cite id="CITEREFWenYingGongLiu2020" class="citation journal cs1">Wen, Fei; Ying, Rendong; Gong, Zheng; Liu, Peilin (February 2020). "Efficient Algorithms for Maximum Consensus Robust Fitting". IEEE Transactions on Robotics. 36 (1): 92–106. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTRO.2019.2943061">10.1109/TRO.2019.2943061</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1941-0468">1941-0468</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:209976632">209976632</a>.</cite>

</li>

<li id="cite_note-:3-23">^ <a href="#cite_ref-:3_23-0">a</a> <a href="#cite_ref-:3_23-1">b</a> <cite id="CITEREFCaiChinKoltun2019" class="citation journal cs1">Cai, Zhipeng; Chin, Tat-Jun; Koltun, Vladlen (2019). <a rel="nofollow" class="external text" href="http://openaccess.thecvf.com/content_ICCV_2019/html/Cai_Consensus_Maximization_Tree_Search_Revisited_ICCV_2019_paper.html">"Consensus Maximization Tree Search Revisited"</a>. Proceedings of IEEE International Conference on Computer Vision (ICCV): 1637–1645. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1908.02021">1908.02021</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2019arXiv190802021C">2019arXiv190802021C</a>.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFBazinSeoPollefeys2013" class="citation book cs1">Bazin, Jean-Charles; Seo, Yongduek; Pollefeys, Marc (2013). "Globally Optimal Consensus Set Maximization through Rotation Search". In Lee, Kyoung Mu; Matsushita, Yasuyuki; Rehg, James M.; Hu, Zhanyi (eds.). Computer Vision – ACCV 2012. Lecture Notes in Computer Science. Vol. 7725. Berlin, Heidelberg: Springer. pp. 539–551. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-37444-9_42">10.1007/978-3-642-37444-9_42</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-37444-9</bdi>.</cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFHartleyKahl2009" class="citation journal cs1">Hartley, Richard I.; Kahl, Fredrik (2009-04-01). "Global Optimization through Rotation Space Search". International Journal of Computer Vision. 82 (1): 64–79. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs11263-008-0186-9">10.1007/s11263-008-0186-9</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1885%2F50831">1885/50831</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1573-1405">1573-1405</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:509788">509788</a>.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFFischlerBolles1981" class="citation journal cs1">Fischler, Martin; Bolles, Robert (1981). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F358669.358692">"Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography"</a>. Communications of the ACM. 24 (6): 381–395. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F358669.358692">10.1145/358669.358692</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:972888">972888</a>.</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite id="CITEREFLeChinErikssonDo2019" class="citation journal cs1">Le, Huu Minh; Chin, Tat-Jun; Eriksson, Anders; Do, Thanh-Toan; Suter, David (2019). "Deterministic Approximate Methods for Maximum Consensus Robust Fitting". IEEE Transactions on Pattern Analysis and Machine Intelligence. 43 (3): 842–857. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1710.10003">1710.10003</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTPAMI.2019.2939307">10.1109/TPAMI.2019.2939307</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1939-3539">1939-3539</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/31494545">31494545</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:29346470">29346470</a>.</cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFBustosChinNeumannFriedrich2019" class="citation arxiv cs1">Bustos, Alvaro Parra; Chin, Tat-Jun; Neumann, Frank; Friedrich, Tobias; Katzmann, Maximilian (2019-02-04). "A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1902.01534">1902.01534</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CV">cs.CV</a>].</cite>

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> <cite id="CITEREFHuberRonchetti2009" class="citation book cs1">Huber, Peter J.; Ronchetti, Elvezio M. (2009-01-29). Robust Statistics. Wiley Series in Probability and Statistics. Hoboken, NJ, USA: John Wiley & Sons, Inc. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2F9780470434697">10.1002/9780470434697</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-470-43469-7</bdi>.</cite>

</li>

<li id="cite_note-:7-30">^ <a href="#cite_ref-:7_30-0">a</a> <a href="#cite_ref-:7_30-1">b</a> <cite id="CITEREFZhouParkKoltun2016" class="citation book cs1">Zhou, Qian-Yi; Park, Jaesik; Koltun, Vladlen (2016). "Fast Global Registration". In Leibe, Bastian; Matas, Jiri; Sebe, Nicu; Welling, Max (eds.). Computer Vision – ECCV 2016. Lecture Notes in Computer Science. Vol. 9906. Cham: Springer International Publishing. pp. 766–782. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-46475-6_47">10.1007/978-3-319-46475-6_47</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-46475-6</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:27362942">27362942</a>.</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> <cite id="CITEREFMacTavishBarfoot2015" class="citation book cs1">MacTavish, Kirk; Barfoot, Timothy D. (2015). "At all Costs: A Comparison of Robust Cost Functions for Camera Correspondence Outliers". 2015 12th Conference on Computer and Robot Vision. pp. 62–69. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FCRV.2015.52">10.1109/CRV.2015.52</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4799-1986-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9305263">9305263</a>.</cite>

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <cite id="CITEREFBosseAgamennoniGilitschenski2016" class="citation journal cs1">Bosse, Michael; Agamennoni, Gabriel; Gilitschenski, Igor (2016). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/8187472">"Robust Estimation and Applications in Robotics"</a>. Foundations and Trends in Robotics. 4 (4). now: 225–269. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1561%2F2300000047">10.1561/2300000047</a>.</cite>

</li>

<li id="cite_note-:8-33">^ <a href="#cite_ref-:8_33-0">a</a> <a href="#cite_ref-:8_33-1">b</a> <cite id="CITEREFBlackRangarajan1996" class="citation journal cs1">Black, Michael J.; Rangarajan, Anand (1996-07-01). "On the unification of line processes, outlier rejection, and robust statistics with applications in early vision". International Journal of Computer Vision. 19 (1): 57–91. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00131148">10.1007/BF00131148</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1573-1405">1573-1405</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7510079">7510079</a>.</cite>

</li>

<li id="cite_note-:9-34">^ <a href="#cite_ref-:9_34-0">a</a> <a href="#cite_ref-:9_34-1">b</a> <cite id="CITEREFBlakeZisserman1987" class="citation book cs1">Blake, Andrew; Zisserman, Andrew (1987). <a rel="nofollow" class="external text" href="https://mitpress.mit.edu/books/visual-reconstruction">Visual reconstruction</a>. The MIT Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780262524063</bdi>.</cite>

</li>

<li id="cite_note-:10-35">^ <a href="#cite_ref-:10_35-0">a</a> <a href="#cite_ref-:10_35-1">b</a> <cite id="CITEREFYangAntonanteTzoumasCarlone2020" class="citation journal cs1">Yang, Heng; Antonante, Pasquale; Tzoumas, Vasileios; Carlone, Luca (2020). "Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection". IEEE Robotics and Automation Letters. 5 (2): 1127–1134. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1909.08605">1909.08605</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FLRA.2020.2965893">10.1109/LRA.2020.2965893</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2377-3774">2377-3774</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:202660784">202660784</a>.</cite>

</li>

<li id="cite_note-icpbesl-36"><a href="#cite_ref-icpbesl_36-0">^</a> <cite id="CITEREFBeslMcKay1992" class="citation journal cs1">Besl, Paul; McKay, Neil (1992). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/3191994">"A Method for Registration of 3-D Shapes"</a>. IEEE Transactions on Pattern Analysis and Machine Intelligence. 14 (2): 239–256. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1992SPIE.1611..586B">1992SPIE.1611..586B</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F34.121791">10.1109/34.121791</a>.</cite>

</li>

<li id="cite_note-kctsin-37">^ <a href="#cite_ref-kctsin_37-0">a</a> <a href="#cite_ref-kctsin_37-1">b</a> <a href="#cite_ref-kctsin_37-2">c</a> <a href="#cite_ref-kctsin_37-3">d</a> <a href="#cite_ref-kctsin_37-4">e</a> <a href="#cite_ref-kctsin_37-5">f</a> <a href="#cite_ref-kctsin_37-6">g</a> <a href="#cite_ref-kctsin_37-7">h</a> <a href="#cite_ref-kctsin_37-8">i</a> <cite id="CITEREFTsinKanade2004" class="citation book cs1">Tsin, Yanghai; Kanade, Takeo (2004). "A Correlation-Based Approach to Robust Point Set Registration". Computer Vision - ECCV 2004. Lecture Notes in Computer Science. Vol. 3023. Springer Berlin Heidelberg. pp. 558–569. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.6729">10.1.1.156.6729</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-24672-5_44">10.1007/978-3-540-24672-5_44</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-21982-8</bdi>.</cite> <code class="cs1-code">{{cite book}}</code>: <code class="cs1-code">|journal=</code> ignored (help)

</li>

<li id="cite_note-fasticp-38"><a href="#cite_ref-fasticp_38-0">^</a> <cite id="CITEREFRusinkiewiczLevoy2001" class="citation conference cs1">Rusinkiewicz, Szymon; Levoy, Marc (2001). Efficient variants of the ICP algorithm. Proceedings of the Third International Conference on 3-D Digital Imaging and Modeling, 2001. IEEE. pp. 145–152. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FIM.2001.924423">10.1109/IM.2001.924423</a>.</cite>

</li>

<li id="cite_note-rpmgold-39">^ <a href="#cite_ref-rpmgold_39-0">a</a> <a href="#cite_ref-rpmgold_39-1">b</a> <a href="#cite_ref-rpmgold_39-2">c</a> <a href="#cite_ref-rpmgold_39-3">d</a> <a href="#cite_ref-rpmgold_39-4">e</a> <cite id="CITEREFGoldRangarajanLuSuguna1998" class="citation journal cs1">Gold, Steven; Rangarajan, Anand; Lu, Chien-Ping; Suguna, Pappu; Mjolsness, Eric (1998). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0031-3203%2898%2980010-1">"New algorithms for 2d and 3d point matching:: pose estimation and correspondence"</a>. Pattern Recognition. 38 (8): 1019–1031. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1998PatRe..31.1019G">1998PatRe..31.1019G</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0031-3203%2898%2980010-1">10.1016/S0031-3203(98)80010-1</a>.</cite>

</li>

<li id="cite_note-gmmjian2-40"><a href="#cite_ref-gmmjian2_40-0">^</a> <cite id="CITEREFJianVemuri2005" class="citation conference cs1">Jian, Bing; Vemuri, Baba C. (2005). A robust algorithm for point set registration using mixture of Gaussians. Tenth IEEE International Conference on Computer Vision 2005. Vol. 2. pp. 1246–1251.</cite>

</li>

<li id="cite_note-cpdmyronenko-41"><a href="#cite_ref-cpdmyronenko_41-0">^</a> <cite id="CITEREFMyronenkoSongCarriera-Perpinán2006" class="citation journal cs1">Myronenko, Andriy; Song, Xubo; Carriera-Perpinán, Miguel A. (2006). <a rel="nofollow" class="external text" href="http://papers.nips.cc/paper/2962-non-rigid-point-set-registration-coherent-point-drift">"Non-rigid point set registration: Coherent point drift"</a>. Advances in Neural Information Processing Systems. 19: 1009–1016. Retrieved 31 May 2014.</cite>

</li>

<li id="cite_note-ohirose1-42"><a href="#cite_ref-ohirose1_42-0">^</a> <cite id="CITEREFHirose2021" class="citation journal cs1">Hirose, Osamu (2021). <a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTPAMI.2020.2971687">"A Bayesian formulation of coherent point drift"</a>. IEEE Transactions on Pattern Analysis and Machine Intelligence. 43 (7): 2269–2286. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTPAMI.2020.2971687">10.1109/TPAMI.2020.2971687</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/32031931">32031931</a>.</cite>

</li>

<li id="cite_note-ohirose2-43"><a href="#cite_ref-ohirose2_43-0">^</a> <cite id="CITEREFHirose2021" class="citation journal cs1">Hirose, Osamu (2021). <a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTPAMI.2020.3043769">"Acceleration of non-rigid point set registration with downsampling and Gaussian process regression"</a>. IEEE Transactions on Pattern Analysis and Machine Intelligence. 43 (8): 2858–2865. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTPAMI.2020.3043769">10.1109/TPAMI.2020.3043769</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/33301401">33301401</a>.</cite>

</li>

<li id="cite_note-44"><a href="#cite_ref-44">^</a> <cite id="CITEREFLiuWuChirikjian2021" class="citation book cs1">Liu, Weixiao; Wu, Hongtao; Chirikjian, Gregory S. (2021). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/9711460">"LSG-CPD: Coherent Point Drift with Local Surface Geometry for Point Cloud Registration"</a>. 2021 IEEE/CVF International Conference on Computer Vision (ICCV). pp. 15273–15282. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2103.15039">2103.15039</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FICCV48922.2021.01501">10.1109/ICCV48922.2021.01501</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-6654-2812-5</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:232404480">232404480</a>.</cite>

</li>

<li id="cite_note-45"><a href="#cite_ref-45">^</a> <cite id="CITEREFPaulyGrossKobbelt2002" class="citation book cs1">Pauly, M.; Gross, M.; Kobbelt, L.P. (2002). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/1183771">"Efficient simplification of point-sampled surfaces"</a>. <a rel="nofollow" class="external text" href="https://infoscience.epfl.ch/record/149331/files/pauly_2002_ESP.pdf">IEEE Visualization, 2002. VIS 2002</a> (PDF). pp. 163–170. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FVISUAL.2002.1183771">10.1109/VISUAL.2002.1183771</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7803-7498-3</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14952977">14952977</a>.</cite>

</li>

<li id="cite_note-46"><a href="#cite_ref-46">^</a> <cite id="CITEREFLiuWuChirikjian2021" class="citation book cs1">Liu, Weixiao; Wu, Hongtao; Chirikjian, Gregory S. (2021). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/9711460">"LSG-CPD: Coherent Point Drift with Local Surface Geometry for Point Cloud Registration"</a>. 2021 IEEE/CVF International Conference on Computer Vision (ICCV). pp. 15273–15282. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2103.15039">2103.15039</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FICCV48922.2021.01501">10.1109/ICCV48922.2021.01501</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-6654-2812-5</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:232404480">232404480</a>.</cite>

</li>

<li id="cite_note-47"><a href="#cite_ref-47">^</a> <cite id="CITEREFAssalih2013" class="citation thesis cs1">Assalih, Hassan. (2013). <a rel="nofollow" class="external text" href="http://www.ros.hw.ac.uk/bitstream/handle/10399/2647/AssalihH_1013_eps.pdf">"Chapter 6: Sorting the Correspondence Space"</a> (PDF). 3D reconstruction and motion estimation using forward looking sonar (Ph.D.). Heriot-Watt University.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <a href="https://commons.wikimedia.org/wiki/Category:Point_set_registration" class="extiw external" title="commons:Category:Point set registration">Point set registration</a>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="http://www.cise.ufl.edu/~anand/students/chui/research.html">Reference implementation of thin plate spline robust point matching</a></li>

<li><a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~ytsin/KCReg/">Reference implementation of kernel correlation point set registration</a></li>

<li><a rel="nofollow" class="external text" href="https://sites.google.com/site/myronenko/research/cpd">Reference implementation of coherent point drift</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/ethz-asl/libpointmatcher">Reference implementation of ICP variants</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/ohirose/bcpd">Reference implementation of Bayesian coherent point drift</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/ChirikjianLab/LSG-CPD">Reference implementation of LSG-CPD</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-23" href="https://en.wikipedia.org/wiki/?title=Point-set_registration&oldid=1297039459">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>